核心任务是通过两次 SPFA(Shortest Path Faster Algorithm) 算法计算一个图中从起点到终点路径上的 最小值 和 最大值,并寻找节点划分使得 最大值 − 最小值 \text{最大值} - \text{最小值} 最大值−最小值 的差值最大。
以下是逐步的详细讲解:
问题描述
输入:
- 一个带权有向图,包含 n n n 个节点和 m m m 条边。
- 每个节点有一个权值 w [ i ] w[i] w[i]。
- 边的方向和连接方式通过输入指定,可能是单向边或双向边。
输出:
- 求一个节点划分,使得从起点 1 1 1 到终点 n n n 的路径上,经过所有点的最小值与反向路径上所有点的最大值之间的差值最大。
算法核心思想
-
计算两条路径的最值:
- 路径 1(正向路径):从起点 1 1 1 出发到图中每个点,找到从起点到达每个节点的最小权值(路径上节点的权值最小值)。
- 路径 2(反向路径):从终点 n n n 出发,找到从终点到每个节点的最大权值(路径上节点的权值最大值)。
-
枚举分界点:
- 设某个节点 i i i 是划分点,则路径 1 的最小值为
dmin[i]
,路径 2 的最大值为dmax[i]
。 - 计算 差值 = d m a x [ i ] − d m i n [ i ] \text{差值} = dmax[i] - dmin[i] 差值=dmax[i]−dmin[i] 并求取最大差值。
- 设某个节点 i i i 是划分点,则路径 1 的最小值为
代码逐步解析
1. 数据结构与变量定义
const int N = 100010, M = 2000010;
int n, m;
int w[N]; // 每个节点的权值
int hs[N], ht[N], e[M], ne[M], idx; // 邻接表存储正向图和反向图
int dmin[N], dmax[N]; // 从起点出发的最小值数组 & 从终点出发的最大值数组
bool st[N]; // 标记节点是否在队列中
queue<int> q; // 队列,用于 SPFA
-
邻接表:
hs
:存储正向图(起点到终点的路径)。ht
:存储反向图(终点到起点的路径)。e
、ne
:链式前向星实现邻接表。
-
路径权值:
dmin[i]
:从起点到节点 i i i 的路径上最小的节点权值。dmax[i]
:从终点到节点 i i i 的路径上最大的节点权值。
2. 图的构建
void add(int h[], int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
- 利用链式前向星存储边,分别存储在
hs
和ht
两个邻接表中。 - 对于每条边,根据输入决定是单向边还是双向边:
add(hs, a, b), add(ht, b, a); if (c == 2) add(hs, b, a), add(ht, a, b); // 双向边
3. SPFA 算法
void spfa(int h[], int dist[], int type) {if (type == 0) { // 求最小值memset(dist, 0x3f, sizeof dmin);dist[1] = w[1]; // 起点权值q.push(1);} else { // 求最大值memset(dist, -0x3f, sizeof dmax);dist[n] = w[n]; // 终点权值q.push(n);}while (q.size()) {int t = q.front();q.pop();st[t] = false;for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (type == 0 && dist[j] > min(dist[t], w[j]) || type == 1 && dist[j] < max(dist[t], w[j])) {if (type == 0) dist[j] = min(dist[t], w[j]); // 更新最小值else dist[j] = max(dist[t], w[j]); // 更新最大值if (!st[j]) {q.push(j);st[j] = true;}}}}
}
-
初始化:
- 对于正向路径,初始化
dmin
,起点的初始值为起点权值w[1]
。 - 对于反向路径,初始化
dmax
,终点的初始值为终点权值w[n]
。
- 对于正向路径,初始化
-
松弛操作:
- 对每条边进行松弛,根据路径类型(最小值或最大值)更新
dist[j]
。
- 对每条边进行松弛,根据路径类型(最小值或最大值)更新
-
入队与出队:
- 如果节点的路径值被更新,则将节点加入队列。
4. 主算法
spfa(hs, dmin, 0); // 正向路径的最小值
spfa(ht, dmax, 1); // 反向路径的最大值// 枚举所有节点作为分界点,求最大差值
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, dmax[i] - dmin[i]);cout << res << endl;
-
调用两次 SPFA:
spfa(hs, dmin, 0)
:计算从起点到每个节点的最小值。spfa(ht, dmax, 1)
:计算从终点到每个节点的最大值。
-
枚举所有节点 i i i,计算 d m a x [ i ] − d m i n [ i ] dmax[i] - dmin[i] dmax[i]−dmin[i] 并更新结果。
算法流程总结
-
构建正向图和反向图:
- 利用链式前向星存储普通边和特殊边。
-
正向路径的最小值计算:
- 通过 SPFA 从起点 1 1 1 计算到每个节点的路径最小值。
-
反向路径的最大值计算:
- 通过 SPFA 从终点 n n n 计算到每个节点的路径最大值。
-
枚举分界点:
- 对于每个节点 i i i,计算 d m a x [ i ] − d m i n [ i ] dmax[i] - dmin[i] dmax[i]−dmin[i],并输出最大值。
时间复杂度
- 图的构建: O ( M ) O(M) O(M)。
- 两次 SPFA: O ( M ) O(M) O(M)(每条边最多入队一次)。
- 枚举分界点: O ( N ) O(N) O(N)。
总复杂度: O ( M + N ) O(M + N) O(M+N)。
输出示例
输入:
5 6
1 2 3 4 5
1 2 0
2 3 0
3 4 0
4 5 0
5 3 2
3 1 2
输出:
4
解释:
- 正向路径的最小值:
dmin = [1, 2, 2, 2, 2]
。 - 反向路径的最大值:
dmax = [5, 5, 5, 5, 4]
。 - 差值 d m a x [ i ] − d m i n [ i ] dmax[i] - dmin[i] dmax[i]−dmin[i] 的最大值为 4 4 4。