ch12 课堂参考代码 及 题目参考思路

课堂参考代码

Bellman-Ford

主要思路：对所有的边进行 n-1 轮松弛操作
单源最短路算法，$O(nm)$

using ll = long long;
const int maxn = 5010, maxm = 5010;
struct Edge {int u, v, w;
} E[maxm];
// d[u]: 当前 s 到 u 的最短路
ll d[maxn];
int n, m;
bool Bf(int s) {memset(d, 0x3f, sizeof(d));d[s] = 0;for (int i = 0; i < n - 1; ++i) {// 使用每条边进行松弛操作for (int j = 0; j < m; ++j) {int u = E[j].u, v = E[j].v, w = E[j].w;d[v] = min(d[v], d[u] + w);}}for (int j = 0; j < m; ++j) {int u = E[j].u, v = E[j].v, w = E[j].w;if (d[v] > d[u] + w) return 1;  // 存在负环}return 0;// 判断负环：做一次以每条边进行松弛操作，如果还能松弛成功就是负环// 注意，如果还能松弛成功是图中存在负环，不是存在从 s 出发能到达的负环
}
int main() {cin >> n >> m;for (int i = 0; i < m; ++i) {cin >> E[i].u >> E[i].v >> E[i].w;}Bf(1);// ... return 0;
}

SPFA

Bellman-ford 算法的队列优化

主要思路：使用每条边进行更新。一个点被更新过才用它的出边进行更新其它点的最短路

单源最短路算法

随机图上平均复杂度 $O(km)$，$k$ 为每个点的平均进队次数 (一般的，k是一个常数，在稀疏图中小于2)

最坏复杂度与 Bellman-Ford 算法相同，$O(nm)$

using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 5010, maxm = 5010;
struct edge {int v, w;
};
vector<edge> G[maxn];
// d[u]: 当前 u 的最短路
ll d[maxn];
int n;
bool inq[maxn];
// cnt: 记录最短路上的路径数
int cnt[maxn];
bool spfa(int s) {memset(d, 0x3f, sizeof(d));memset(inq, 0, sizeof(inq));queue<int> q;// 把源点 s 入队d[s] = 0, cnt[s] = 0, q.push(s), inq[s] = 1;while (!q.empty()) {int u = q.front();q.pop(), inq[u] = 0;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i].v, w = G[u][i].w;// 如果松弛操作成功才入队if (d[v] > d[u] + w) {d[v] = d[u] + w;// v 的最短路上路径数为 u 最短路上路径数 + 1cnt[v] = cnt[u] + 1;if (cnt[v] >= n) return 1;  // 存在负环// 保证不会重复出现在队列if (!inq[v]) {q.push(v), inq[v] = 1;}}}}return 0;
}
int main() {// s 为单源最短路的源点int m, u, v, w, s = 1;cin >> n >> m;for (int i = 0; i < m; ++i) {cin >> u >> v >> w;G[u].push_back({v, w});// 注意看题目是否是双向边}spfa(1);// ...return 0;
}

Floyd-Warshall

多源最短路算法，$O(n^3)$

using ll = long long;
const int maxn = 410;
ll d[maxn][maxn];
int main() {int n;cin >> n;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cin >> d[i][j];}}for (int k = 1; k <= n; ++k) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}// ...return 0;
}

总结

• 单源最短路算法
  • Dijkstra：适用于边权非负的图，时间复杂度 $O(m\log m)$
  • Bellman-Ford：可用于任意图，能判断负环，时间复杂度 $O(nm)$ ，一般不用，直接用 SPFA
  • SPFA：适用范围与 Bellman-Ford 相同，随机图效率很高，但最坏复杂度 $O(nm)$
• 全局最短路算法
  • Floyd：可用于任意图，能判断负环，时间复杂度 $O(n^3)$

ch12 部分题目解法

炼金术士小图 II

• 分析：

  • 这里处理技巧与 ch10 章节中题目 【Watering Hole】中的类似，考虑设定一个超级源点，编号记为 n+1
  • n 种材料看作 n 个结点，再加一个编号为 n + 1 的结点表示起点（什么材料都没有），花费作为边权，问题转换为从起点到结点 n 的单源最短路问题
  • 建图
    • 从起点 n + 1 向代表材料的每个结点 i 连一条边权为 $p_i$ 的有向边，表示可以花费 $p_i$ 从“什么都没有”到“拥有材料 i”。
    • 对于 type = 1 类型的转化，从结点 $a_i$ 向 $b_i$ 连一条边权为 $c_i$ 的有向边。
    • 对于 type = 2 类型的分解，从结点 $a_i$ 向 $b_i$ 连一条边权为 $-c_i$ 的有向边。（花费 $-c_i$ 就表示赚取 $c_i$）
  • 跑 SPFA 求从起点 n + 1 到 n 的最短路。
    • 如果存在负环，说明可以赚取无限的利润。
    • 如果 d[n] < 0 ，说明得到材料 n 花费负数费用，即赚取了利润。
  • 注意整个图有 n + 1 个结点，负环的判断应该是存在边数 >= n+1 的最短路，而不是 >= n。（写 >= n 也不会出错，因为起点只有出边没有入边，不会在环中）

• 代码

  int main() {int m, pi;cin >> n >> m;// 每个点都和 n+1 节点相连for (int i = 1; i <= n; i++) {cin >> pi;G[n + 1].push_back({i, pi});}for (int i = 1; i <= m; i++) {int t, a, b, c;cin >> t >> a >> b >> c;if (t == 1)G[a].push_back({b, c});elseG[a].push_back({b, -c});}// 从 n + 1 节点出发跑 spfa 算法// 计算到达 n 号节点的最短路长度bool flag = spfa(n + 1);if (flag || d[n] < 0) // 有负环 或 到 n 的最短路为负则存在利润cout << "lucky" << endl;elsecout << d[n] << endl;return 0;
  }
  

  路况查询

• 分析：

  • 因为查询次数 q 较大，如果对于每次查询都去跑一次单源最短路，时间复杂度较高。

  • 本题是对于 Floyd 原理的应用。允许经过结点 k 时，Floyd 算法执行了以下代码

    for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {f[i][j] = min(f[i][j], f[i][k] + f[k][j]);}
    }
    

    那么城市 x 解封时，表示允许经过结点 x ，将以上代码 k 改为 x 执行一遍即可。

  • 对于 type = 2 类型的询问

    • 先判断 x 和 y 的解封情况，可以通过 bool 数组标记和判断。
    • x 或 y 还未解封， 或 f[x][y] == 正无穷大，说明无法到达。
    • 否则输出 f[x][y] 。

• 代码：详见课本【例12.4】路况查询

Cow Hurdles

• 分析：

  • 最短路问题是希望路径边权之和最小，本题希望路径中的最大边权最小，只需要修改松弛操作即可。

  • 从数据范围看出如果每次询问跑一遍单源最短路，效率较低，用 Floyd 算法比较合适。

  • f[i][j] 原本表示 i 到 j 的路径中，最小的路径长度，改为表示 i 到 j 的路径中，最小的最大边权。

  • 将 Floyd 的状态转移从

    f[i][j] = min(f[i][j], f[i][k] + f[k][j])
    

    改为

    f[i][j] = min(f[i][j], max(f[i][k], f[k][j]))
    

    即可

    • f[i][k] + f[k][j] 表示经过 k 的路径中 i 到 j 的最短路长度，求路径总长度所以用加法。
    • max(f[i][k], f[k][j]) 是从经过 k 的路径中 i 到 j 的最大边权。

  • 最后如果 f[a][b] == 正无穷大，表示无法从 a 到达 b，输出 -1，否则输出 f[a][b] 。

• 代码：详见课本【例12.3】跳跃比赛