bellman_ford之判断负权回路
城市间货物运输 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
提示信息
路径中存在负权回路，从 1 -> 2 -> 3 -> 1，总权值为 -1，理论上货物运输商可以在该回路无限循环赚取政府补贴，所以输出 “circle” 表示已经检测出了该种情况。
数据范围：
1 <= n <= 1000；
1 <= m <= 10000;-100 <= v <= 100;
解题思路
先正常跑 n−1 轮 Bellman-Ford，得到 dist
再跑 第 n 轮：
- 看还能不能被松弛
- 能松弛的点 = 受到负权回路影响的点
从这些“受影响的点”出发，看能不能到终点 n并且能否从1到这些点
如果能到：
- 说明可以：
1 -> ... -> 负环 -> ... -> n - 可以无限压低成本 → 输出 “circle”
如果不能到：
- 这个负环 不会影响 1→n 的最短路结果
- 就输出正常的最短路 or unconnected
import java.util.*;
public class Main {
static class Edge {
int from, to, w;
Edge(int f, int t, int w) {
this.from = f;
this.to = t;
this.w = w;
}
}
static final int INF = 0x3f3f3f3f;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
List<Edge> edges = new ArrayList<>();
List<Integer>[] graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
for (int i = 0; i < m; i++) {
int s = in.nextInt();
int t = in.nextInt();
int v = in.nextInt();
edges.add(new Edge(s, t, v));
graph[s].add(t); // 仅用于后面 BFS 可达性判断
}
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
dist[1] = 0;
// Step 1：标准 Bellman-Ford，跑 n-1 轮
for (int k = 1; k <= n - 1; k++) {
boolean updated = false;
for (Edge e : edges) {
if (dist[e.from] != INF && dist[e.to] > dist[e.from] + e.w) {
dist[e.to] = dist[e.from] + e.w;
updated = true;
}
}
if (!updated) break;
}
// Step 2：第 n 轮，找还能继续被松弛的点 —— 负环影响点
boolean[] neg = new boolean[n + 1];
for (Edge e : edges) {
if (dist[e.from] != INF && dist[e.to] > dist[e.from] + e.w) {
neg[e.to] = true;
}
}
// Step 3：从所有 neg 点出发，检查是否能到达 n
boolean[] vis = new boolean[n + 1];
Queue<Integer> q = new ArrayDeque<>();
for (int i = 1; i <= n; i++) {
if (neg[i]) {
q.offer(i);
vis[i] = true;
}
}
boolean affect = false;
while (!q.isEmpty()) {
int u = q.poll();
if (u == n) {
affect = true;
break;
}
for (int v : graph[u]) {
if (!vis[v]) {
vis[v] = true;
q.offer(v);
}
}
}
if (affect) {
System.out.println("circle");
} else if (dist[n] == INF) {
System.out.println("unconnected");
} else {
System.out.println(dist[n]);
}
}
}
bellman_ford之单源有限最短路
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
提示信息
从 2 -> 5 -> 6 中转一站，运输成本为 0。
1 <= n <= 1000；
1 <= m <= 10000;
-100 <= v <= 100;
解题思路
import java.util.*;
public class Main {
static class Edge {
int from, to, value;
Edge(int f, int t, int value) {
this.from = f;
this.to = t;
this.value = value;
}
}
static final int INF = 0x3f3f3f3f;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < m; i++) {
int s = in.nextInt();
int t = in.nextInt();
int v = in.nextInt();
edges.add(new Edge(s, t, v));
}
int src = in.nextInt();
int dst = in.nextInt();
int k = in.nextInt();
// prev[v]：在当前限制（使用的边数）下，从 src 到 v 的最小成本
int[] prev = new int[n + 1];
Arrays.fill(prev, INF);
prev[src] = 0; // 起点，0 条边时只能在 src
// 每一轮相当于允许多使用一条边
for (int step = 1; step <= k + 1; step++) {
// cur 是这一轮更新后的结果，先复制上一轮
int[] cur = prev.clone(); // 关键：时间层隔离
// 尝试用“上一层的路径 + 一条边”来更新本层的距离
for (Edge e : edges) {
if (prev[e.from] != INF) {
int newDist = prev[e.from] + e.value;
if (newDist < cur[e.to]) {
cur[e.to] = newDist;
}
}
}
// 推进到下一层
prev = cur;
}
if (prev[dst] == INF) {
// 在给定的中转次数限制下，到不了 dst
System.out.println("unreachable");
} else {
// 找到了最小运输成本（可能是负数 = 盈利）
System.out.println(prev[dst]);
}
}
}
评论