Acwing341

核心任务是通过两次 SPFA（Shortest Path Faster Algorithm） 算法计算一个图中从起点到终点路径上的 最小值 和 最大值，并寻找节点划分使得 $\text{最大值}-\text{最小值}$ 的差值最大。

以下是逐步的详细讲解：

---

问题描述

输入：

• 一个带权有向图，包含 $n$ 个节点和 $m$ 条边。
• 每个节点有一个权值 $w[i]$。
• 边的方向和连接方式通过输入指定，可能是单向边或双向边。

输出：

• 求一个节点划分，使得从起点 $1$ 到终点 $n$ 的路径上，经过所有点的最小值与反向路径上所有点的最大值之间的差值最大。

---

算法核心思想

1. 计算两条路径的最值：

   • 路径 1（正向路径）：从起点 $1$ 出发到图中每个点，找到从起点到达每个节点的最小权值（路径上节点的权值最小值）。
   • 路径 2（反向路径）：从终点 $n$ 出发，找到从终点到每个节点的最大权值（路径上节点的权值最大值）。

2. 枚举分界点：

   • 设某个节点 $i$ 是划分点，则路径 1 的最小值为 dmin[i]，路径 2 的最大值为 dmax[i]。
   • 计算 $\text{差值}=dmax[i]-dmin[i]$ 并求取最大差值。

---

代码逐步解析

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

1. 邻接表：

   • hs：存储正向图（起点到终点的路径）。
   • ht：存储反向图（终点到起点的路径）。
   • e、ne：链式前向星实现邻接表。

2. 路径权值：

   • dmin[i]：从起点到节点 $i$ 的路径上最小的节点权值。
   • dmax[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：

  1. spfa(hs, dmin, 0)：计算从起点到每个节点的最小值。
  2. spfa(ht, dmax, 1)：计算从终点到每个节点的最大值。

• 枚举所有节点 $i$，计算 $dmax[i]-dmin[i]$ 并更新结果。

---

算法流程总结

1. 构建正向图和反向图：

   • 利用链式前向星存储普通边和特殊边。

2. 正向路径的最小值计算：

   • 通过 SPFA 从起点 $1$ 计算到每个节点的路径最小值。

3. 反向路径的最大值计算：

   • 通过 SPFA 从终点 $n$ 计算到每个节点的路径最大值。

4. 枚举分界点：

   • 对于每个节点 $i$，计算 $dmax[i]-dmin[i]$，并输出最大值。

---

时间复杂度

1. 图的构建：$O(M)$。
2. 两次 SPFA：$O(M)$（每条边最多入队一次）。
3. 枚举分界点：$O(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]。
• 差值 $dmax[i]-dmin[i]$ 的最大值为 $4$。

原文地址：https://blog.csdn.net/ailbj/article/details/143835755

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！