代码随想录算法训练营 Day52 | 图论 part10

94. 城市间货物运输 I

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v （单向图）。

输出描述

如果能够从城市 1 到连通到城市 n， 请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 "unconnected"。

输入示例

6 7 5 6 -2 1 2 1 5 3 1 2 5 2 2 4 -3 4 6 4 1 3 5

输出示例

1

#include <iostream> #include <vector> #include <queue> using namespace std; // 表示一个较大的数，作为“无穷大” const int INF = 1e6; // 边结构体 struct Edge { int t; // 边的终点 int v; // 边的权值 Edge(int t, int v) : t(t), v(v) {} }; int main() { int n, m; cin >> n >> m; // n 表示点数，m 表示边数 // 邻接表存图，edges[i] 表示从点 i 出发的所有边 vector<vector<Edge>> edges(n + 1); // 输入 m 条有向边 for (int i = 0; i < m; i++) { int s, t, v; cin >> s >> t >> v; // s -> t，权值为 v edges[s].push_back(Edge(t, v)); } int start = 1, end = n; // 起点为 1，终点为 n // minDist[i] 表示从起点到点 i 的最短距离 vector<int> minDist(n + 1, INF); // visited[i] 表示点 i 是否已经在队列中 // 注意：这里的 visited 更准确地说应该叫 inQueue vector<bool> visited(n + 1, false); queue<int> que; // 初始化起点 que.push(start); minDist[start] = 0; visited[start] = true; // SPFA 算法主体 while (!que.empty()) { int cur = que.front(); que.pop(); // 当前点出队，标记为不在队列中 visited[cur] = false; // 遍历当前点的所有出边 for (Edge edge : edges[cur]) { int s = cur; // 当前起点 int t = edge.t; // 边的终点 int v = edge.v; // 边的权值 // 松弛操作： // 如果经过 s 到 t 的路径更短，就更新 minDist[t] if (minDist[t] > minDist[s] + v) { minDist[t] = minDist[s] + v; // 如果 t 不在队列中，就加入队列 if (!visited[t]) { que.push(t); visited[t] = true; } } } } // 输出结果 if (minDist[end] == INF) cout << "unconnected" << endl; else cout << minDist[end] << endl; return 0; }

总结

1. 算法简介

这段代码实现的是 SPFA 算法，用于求有向图中从1号点到n号点的最短路径。

SPFA 可以看作是 Bellman-Ford 算法的队列优化版本。它的核心思想是：
如果某个点的最短距离被更新了，那么从这个点出发的边也可能继续更新其他点，所以把这个点放进队列中继续处理。

2. 代码思路

首先使用邻接表存图：

vector<vector<Edge>> edges(n + 1);

其中edges[s]存储所有从s出发的边。

然后初始化距离数组：

vector<int> minDist(n + 1, INF); minDist[start] = 0;

表示起点到自己的距离是0，到其他点的距离暂时认为是无穷大。

接着从起点开始入队，不断取出队首节点，对它的所有出边进行松弛：

if (minDist[t] > minDist[s] + v) { minDist[t] = minDist[s] + v; }

如果一个点的距离被更新，并且它当前不在队列中，就将它加入队列，等待后续继续扩展。

3. 变量说明

minDist[i]：表示从起点1到点i的最短距离。

visited[i]：表示点i当前是否在队列中。这里命名为visited容易误解，更推荐改名为inQueue。

queue<int> que：用于存储需要继续松弛的节点。

4. 算法特点

SPFA 可以处理 负权边，但不能处理 负权环。如果图中存在从起点可达的负权环，最短路会不断变小，算法可能无法正常结束。

平均情况下 SPFA 表现不错，但最坏情况下时间复杂度仍然可能退化到：

O(n * m)

其中n是点数，m是边数。

95. 城市间货物运输 II

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

然而，在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时，存在一种情况：图中可能出现负权回路。负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴，算法还需检测这种特殊情况。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。

城市 1 到城市 n 之间可能会出现没有路径的情况

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v。

输出描述

如果没有发现负权回路，则输出一个整数，表示从城市1到城市n的最低运输成本（包括政府补贴）。如果该整数是负数，则表示实现了盈利。如果发现了负权回路的存在，则输出 "circle"。如果从城市 1 无法到达城市 n，则输出 "unconnected"。

输入示例

4 4 1 2 -1 2 3 1 3 1 -1 3 4 1

输出示例

circle

#include <iostream> #include <vector> #include <queue> using namespace std; // 定义一个较大的数，表示无穷大 const int INF = 1e6; // 边结构体 struct Edge { int t; // 边的终点 int v; // 边的权值 Edge(int t, int v) : t(t), v(v) {} }; int main() { int n, m; cin >> n >> m; // n 表示点数，m 表示边数 // 使用邻接表存图 // edges[i] 表示从点 i 出发的所有边 vector<vector<Edge>> edges(n + 1); // 输入 m 条有向边 for (int i = 0; i < m; i++) { int s, t, v; cin >> s >> t >> v; // s -> t，权值为 v edges[s].push_back(Edge(t, v)); } int start = 1, end = n; // 起点为 1，终点为 n bool flag = true; // 用来标记是否存在负权环 // minDist[i] 表示从起点到点 i 的最短距离 vector<int> minDist(n + 1, INF); // visited[i] 表示点 i 当前是否在队列中 // 更准确的命名可以是 inQueue vector<bool> visited(n + 1, false); // count[i] 表示点 i 入队的次数 // 如果某个点入队次数达到 n，说明存在负权环 vector<int> count(n + 1, 0); queue<int> que; // 初始化起点 que.push(start); minDist[start] = 0; count[start] = 1; // 建议加上这一句，使 visited 的含义更加严谨 visited[start] = true; // SPFA 算法主体 while (!que.empty()) { int cur = que.front(); que.pop(); // 当前点出队，标记为不在队列中 visited[cur] = false; // 遍历当前点的所有出边 for (Edge edge : edges[cur]) { int s = cur; // 当前点 int t = edge.t; // 边的终点 int v = edge.v; // 边的权值 // 松弛操作 // 如果从 s 到 t 可以得到更短距离，就更新 minDist[t] if (minDist[t] > minDist[s] + v) { minDist[t] = minDist[s] + v; // 如果 t 当前不在队列中，就加入队列 if (!visited[t]) { que.push(t); visited[t] = true; // 记录 t 的入队次数 count[t]++; // 如果某个点入队次数达到 n， // 说明存在从起点可达的负权环 if (count[t] == n) { flag = false; // 清空队列，提前结束算法 while (!que.empty()) que.pop(); break; } } } } } // 根据结果输出 if (!flag) cout << "circle" << endl; // 存在负权环 else if (minDist[end] == INF) cout << "unconnected" << endl; // 起点无法到达终点 else cout << minDist[end] << endl; // 输出最短路径 return 0; }

总结

1. 算法简介

这段代码实现的是 带负权环判断的 SPFA 算法。

它不仅可以求从1号点到n号点的最短路径，还可以判断从起点出发是否能够到达某个 负权环。

如果存在负权环，最短路径会被不断变小，此时最短路没有实际意义，程序输出：

circle

2. 存图方式

代码使用邻接表存储有向图：

vector<vector<Edge>> edges(n + 1);

其中edges[s]表示从点s出发的所有边。

每条边用结构体Edge表示：

struct Edge { int t; int v; };

t表示终点，v表示边权。

3. SPFA 核心思想

SPFA 的核心是 松弛操作。

如果当前点s到终点t可以得到更短路径，就更新minDist[t]：

if (minDist[t] > minDist[s] + v) { minDist[t] = minDist[s] + v; }

一旦某个点的最短距离被更新，它后面的边也可能继续影响其他点，所以需要将这个点加入队列继续处理。

4. 队列优化

代码中使用queue<int>存储需要继续处理的节点：

queue<int> que;

同时用visited数组判断某个点是否已经在队列中：

vector<bool> visited(n + 1, false);

这样可以避免同一个点重复入队，提高效率。

不过这里的visited更准确地说不是“访问过”，而是“是否在队列中”，所以命名为inQueue会更清晰。

5. 负权环判断

代码使用count[i]记录点i的入队次数：

vector<int> count(n + 1, 0);

在一个没有负权环的图中，最短路最多经过n - 1条边。

如果某个点被反复更新，并且入队次数达到n，就说明存在负权环：

if (count[t] == n) { flag = false; }

此时程序认为最短路不存在，输出：

circle

6. 总结

这份代码是在普通 SPFA 的基础上，加入了 入队次数统计，从而实现了负权环判断。

整体流程可以概括为：

建图 → 初始化距离 → 队列松弛 → 统计入队次数 → 判断负权环 → 输出结果

96. 城市间货物运输 III

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v。

最后一行包含三个正整数，src、dst、和 k，src 和 dst 为城市编号，从 src 到 dst 经过的城市数量限制。

输出描述

输出一个整数，表示从城市 src 到城市 dst 的最低运输成本，如果无法在给定经过城市数量限制下找到从 src 到 dst 的路径，则输出 "unreachable"，表示不存在符合条件的运输方案。

输入示例

6 7 1 2 1 2 4 -3 2 5 2 1 3 5 3 5 1 4 6 4 5 6 -2 2 6 1

输出示例

0

#include <iostream> #include <vector> using namespace std; // 定义一个较大的数，表示无穷大 const int INF = 1e8; int main() { int n, m; cin >> n >> m; // n 表示点数，m 表示边数 // 使用边集数组存图 // 每条边格式为：{起点, 终点, 权值} vector<vector<int>> edges; // 输入 m 条有向边 for (int i = 0; i < m; i++) { int s, t, v; cin >> s >> t >> v; // s -> t，权值为 v edges.push_back({s, t, v}); } int src, dst, k; cin >> src >> dst >> k; // 起点、终点、最多经过 k 个中转点 // minDist[i] 表示从 src 到 i 的最短距离 vector<int> minDist(n + 1, INF); // minDist_copy 用来保存上一轮的最短距离 // 防止一轮中连续松弛，导致经过的边数超过限制 vector<int> minDist_copy(n + 1); // 起点到自己的距离为 0 minDist[src] = 0; // 最多经过 k 个中转点，等价于最多经过 k + 1 条边 for (int i = 1; i <= k + 1; i++) { // 保存上一轮结果 minDist_copy = minDist; // 遍历所有边，进行松弛操作 for (auto& edge : edges) { int s = edge[0]; // 边的起点 int t = edge[1]; // 边的终点 int v = edge[2]; // 边的权值 // 只有上一轮中 s 可达，才可以用 s 去更新 t if (minDist_copy[s] != INF && minDist[t] > minDist_copy[s] + v) { minDist[t] = minDist_copy[s] + v; } } } // 输出结果 if (minDist[dst] == INF) cout << "unreachable" << endl; // 无法到达 else cout << minDist[dst] << endl; // 输出最短距离 return 0; }

总结

1. 算法简介

这段代码使用的是 Bellman-Ford 算法的限制边数版本。

它解决的问题是：
从src出发，到达dst，在最多经过k个中转点的情况下，求最短路径。

最多经过k个中转点，等价于最多走：

k + 1 条边

所以代码中循环执行了k + 1轮松弛。

2. 存图方式

代码使用边集数组存图：

vector<vector<int>> edges;

每条边存成一个三元组：

{s, t, v}

含义是：

从 s 到 t 有一条权值为 v 的有向边

这种存图方式非常适合 Bellman-Ford，因为 Bellman-Ford 每一轮都需要遍历所有边。

3. 核心状态

核心数组是：

vector<int> minDist(n + 1, INF);

其中：

minDist[i] 表示从 src 到 i 的当前最短距离

初始化时：

minDist[src] = 0;

表示起点到自己的距离为0，其他点暂时不可达。

4. 为什么需要 minDist_copy

这段代码里最关键的是：

minDist_copy = minDist;

每一轮松弛时，都使用上一轮的minDist_copy来更新当前的minDist。

这样做是为了限制路径使用的边数。

如果不用minDist_copy，那么在同一轮循环中，一个刚刚被更新的点可能立刻继续更新其他点，导致一轮内走了多条边，从而破坏k + 1条边的限制。

5. 松弛操作

核心松弛逻辑是：

if (minDist_copy[s] != INF && minDist[t] > minDist_copy[s] + v) { minDist[t] = minDist_copy[s] + v; }

意思是：

如果上一轮中src可以到达s，并且通过s -> t可以让到达t的距离更短，那么就更新minDist[t]。

这就是 Bellman-Ford 的核心思想。

6. 复杂度分析

外层循环执行k + 1次，每次遍历所有边。

所以时间复杂度是：

O((k + 1) * m)

空间复杂度主要来自距离数组和边集数组：

O(n + m)

7. 总结

这段代码可以概括为：

边集存图 → 初始化距离 → 限制 k + 1 轮松弛 → 判断终点是否可达