Loading... # ACWing 342 道路与航线 题解 ## 题目描述 Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 $T$ 个城镇 ( $1 \le T \le 25,000$ )，编号为 $1$ 到 $T$ 。这些城镇之间通过 $R$ 条道路 ( $1 \le R \le 50,000$ ，编号为 $1$ 到 $R$ ) 和 $P$ 条航线 ( $1 \le P \le 50,000$ ，编号为 $1$ 到 $P$ ) 连接。每条道路 $i$ 或者航线 $i$ 连接城镇 $A_i$ ( $1 \le A_i \le T$ )到 $B_i$ ( $1 \le B_i \le T$ )，花费为 $C_i$ 。 对于道路 $0 \le C_i \le 10,000$ ;然而航线的花费很神奇，花费 $C_i$ 可能是负数( $-10,000 \le C_i \le 10,000$ )。道路是双向的，可以从 $A_i$ 到 $B_i$，也可以从 $B_i$ 到 $A_i$ ，花费都是 $C_i$ 。然而航线与之不同，只可以从 $A_i$ 到 $B_i$ 。 事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台 了一些政策保证：如果有一条航线可以从 $A_i$ 到 $B_i$，那么保证不可能通过一些道路和航线从 $B_i$ 回到 $A_i$ 。由于 $FJ$ 的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇 $S$ ( $1 \le S \le T$) 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。 ## 输入 共 $R+P+1$ 行 第 $1$ 行：四个整数 $T$ , $R$ , $P$ 和 $S$ ，分别表示城镇的数量，道路的数量，航线的数量和中心城镇。 第 $2$ 到 $R+1$ 行：每行三个整数 $A_i$ , $B_i$ 和 $C_i$ ，描述一条道路。 第 $R+2$ 到 $R+P+1$ 行：每行三个整数 $A_i$ , $B_i$ 和 $C_i$ ，描述一条航线。 ## 输出 共 $T$ 行，第 $i$ 行输出城市 $S$ 到城市 $i$ 的最小花费。如果不能到达，输出`NO PATH` ## 解题思路 拿到本题， 由于存在负权边， 首先考虑的解题思路为spfa。但实际测试发现， 这道题的数据卡掉了spfa, 因此需要考虑其他的解题方式。 注意到在题干中道路的边权均为正数， 而航道的边权可正可负， 因此考虑从这里入手。 题目中写道:**如果有一条航线可以从 $A_i$ 到 $B_i$，那么保证不可能通过一些道路和航线从 $B_i$ 回到 $A_i$ 。**这意味着如果除去所有的航线，则图会被分割为若干个由无限边构成的子图， 且$A_i$和$B_i$所在的子图一定不连通。下面给出证明： - 已知如果$A_i$和$B_i$通过一条单向边连接， 则不存在从$B_i$到$A_i$的路径， - 如果不存在另外的从$A_i$到$B_i$的路径， 则$A_i$和$B_i$所在的子图一定不连通 - 如果存在另外的从$A_i$到$B_i$的路径， 则这条路径上一定存在单向边 - 假设这条路径上不存在单向边， 则存在从$B_i$到$A_i$的路径， 此时与题干相矛盾 - 去除掉这条路径上的单向边， 则$A_i$和$B_i$一定不连通 - 因此， 如果去除掉所有的单向边， 得到的图一定是由若干个仅有无向边组成的强连通分量， 而每个强连通分量之间的连接是通过若干条有向边实现的 由于每个连通分量之间的连通方式都是单向链接， 因此满足拓扑序， 可以顺序处理每个连通分量， 在每个连通分量内部采用dijstra算法， 连通分量之间利用拓扑排序求解。 代码解释： - 在代码实现中对于下列数组的解释如下： - `id`数组存储了每个节点对应的连通分量的标识 - `group`数组存储了每个连通分量的所有的节点 - `indegree`数组存储了每一个连通分量的入度 - 更新最短距离的整体过程 - 首先先将起点$s$的距离置为$0$， 将$s$加入优先队列 - 然后寻找入度为$0$的强连通分量， 将其入队 - 当队列不空时， 取出队头对应的强连通分量， 将其内部的所有的节点加入优先队列 - 执行堆优化的dijstra算法 - 在算法执行过程， 更新节点的最小值时， 需要判断一下边的始点和终点是否相同，如果不相同还要将终点所在的强连通分量的入度减一， 当终点所在的强连通分量为0的时候， 将终点加入队列 ## AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <queue> #define endl '\n' using namespace std; const int N = 2e5 + 10; typedef pair<int, int> PII; int n, r, p, s; int h[N], e[N], ne[N], w[N], idx; int cnt; int id[N]; vector<int> group[N]; int dist[N]; bool st[N]; int indegree[N]; queue<int> q; void add(int a, int b, int c) { e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx ++; } void dfs(int u, int idx) { id[u] = idx; group[idx].push_back(u); for(int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if(st[j]) continue; st[j] = true; dfs(j, idx); } } void dijstra(int idx) { priority_queue<PII, vector<PII>, greater<PII>> heap; for(auto t : group[idx]) { heap.push({dist[t], t}); } while(heap.size()) { auto t = heap.top(); heap.pop(); int d = t.first, u = t.second; if(st[u]) continue; st[u] = true; for(int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if(id[u] != id[j]) { indegree[id[j]] --; if(indegree[id[j]] == 0) q.push(id[j]); } if(dist[j] > dist[u] + w[i]) { dist[j] = dist[u] + w[i]; if(id[u] == id[j]) heap.push({dist[j], j}); } } } } void topsort() { memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); dist[s] = 0; for(int i = 1; i <= cnt; i ++) { if(indegree[i]) continue; q.push(i); } while(q.size()) { int t = q.front(); q.pop(); dijstra(t); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(h, -1, sizeof h); cin >> n >> r >> p >> s; for(int i = 1; i <= r; i ++) { int a, b, c; cin >> a >> b >> c; add(a, b, c); add(b, a, c); } for(int i = 1; i <= n; i ++) { if(st[i]) continue; st[i] = true; dfs(i, ++ cnt); } // for(int i = 1; i <= n; i ++) cout << id[i] << ' '; for(int i = 1; i <= p; i ++) { int a, b, c; cin >> a >> b >> c; add(a, b, c); indegree[id[b]] ++; } // for(int i = 1; i <= cnt; i ++) cout << indegree[i] << ' '; topsort(); for(int i = 1; i <= n; i ++) { if(dist[i] > 0x3f3f3f3f / 2) cout << "NO PATH" << endl; else cout << dist[i] << endl; } return 0; } ``` 最后修改：2025 年 03 月 12 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏