2019ICPC(银川) – Delivery Route（强连通分量 + 拓扑排序 + dijkstra）
- 2020 年 4 月 7 日
- 筆記
题目：有n个派送点，x条双向边，y条单向边，出发点是s，双向边的权值均为正，单向边的权值可以为负数，对于单向边给出了一个限制：如果u->v成立，则v->u一定不成立。问，从s出发，到其他所有点的最短路是多少（包括s）。
思路：对于单向边的限制，我们可以这么理解：双向边相连接的点一定组成一个强连通分量，如果一条单向边存在于某个强连通分量中，可以得出：如果“u -> v”，则一定“v -> u”，可以推出单向边一定只存在于连接两个强连通分量，且还可以推出，强连通分量缩点后，连上单项边，此时的图一定是一个有向无环图，于是给出的限制”对于单向边给出了一个限制：如果u->v成立，则v->u一定不成立。”完全成立，于是图的性质我们分析完了。
①似乎这个图的性质可以直接跑dijkstra，的确可以，但是负权边的存在复杂度太大。
②每个强连通分量都可以dijkstra，且图存在拓扑排序，不如让入度为0的缩点先跑dijkstra，然后一条单向边只影响其他强连通分量的一个点的距离，然后按照拓扑序来确定每个强连通分量跑dijkstra的顺序。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <queue> 5 6 #define ll long long 7 #define pb push_back 8 #define fi first 9 #define se second 10 11 using namespace std; 12 13 const int N = 25000 + 10; 14 const int M = 50000 + 10; 15 const ll INF = 1e10; 16 struct Edge{ 17 int to, nxt, w; 18 }e[M << 2]; 19 struct node{ 20 int u, v, w; 21 }; 22 struct tmp{ 23 int now; 24 ll w; 25 bool friend operator<(const tmp& a, const tmp& b){ 26 return a.w > b.w; 27 } 28 }; 29 int head[N], scc[N], du[N], vis[N], ok[N]; 30 ll dis[N]; 31 vector<node > vp[N];//单向边 32 vector<int > belong[N];//属于哪个scc 33 vector<int > mp[N];//存边 34 priority_queue<tmp > pque; 35 int n, x, y, s, tot, col; 36 37 inline void add(int u, int v, int w){ 38 e[tot].to = v; e[tot].nxt = head[u]; 39 e[tot].w = w; head[u] = tot++; 40 } 41 42 //缩点 43 void dfs(int now){ 44 scc[now] = col; 45 belong[col].pb(now); 46 for(int o = head[now]; ~o; o = e[o].nxt) 47 if(!scc[e[o].to]) dfs(e[o].to); 48 } 49 50 //检测这个点是不是有效点 51 void check(int now){ 52 ok[now] = 1; 53 for(auto to : mp[now]) 54 if(!ok[to]) check(to); 55 } 56 57 void dijkstra(int ss){ 58 while(!pque.empty()) pque.pop(); 59 if(ss == s) pque.push({ss, dis[ss]}); //图一定是从出发点s开始的 60 else{ 61 //相当于从一个超级源点出发 62 for(auto it : belong[scc[ss]]) pque.push({it, dis[it]}); 63 } 64 while(!pque.empty()){ 65 int u = pque.top().now; 66 pque.pop(); 67 if(vis[u]) continue; 68 vis[u] = 1; 69 for(int o = head[u]; ~o; o = e[o].nxt){ 70 if(dis[u] + e[o].w < dis[e[o].to]){ 71 dis[e[o].to] = dis[u] + e[o].w; 72 pque.push({e[o].to, dis[e[o].to]}); 73 } 74 } 75 } 76 } 77 78 void top_sort(){ 79 queue<int > que; 80 que.push(scc[s]);//满足的图 应该是从s的连通图出发的拓扑图 81 dijkstra(s); 82 while(!que.empty()){ 83 int inx = que.front(); 84 que.pop(); 85 for(auto it : vp[inx]){ 86 //一条单向边影响一个点的距离 87 if(dis[it.u] + it.w < dis[it.v]){ 88 dis[it.v] = dis[it.u] + it.w; 89 } 90 //入度0，跑dijkstra 91 if(--du[scc[it.v]] == 0){ 92 que.push(scc[it.v]); 93 dijkstra(it.v); 94 } 95 } 96 } 97 } 98 99 100 void solve(){ 101 scanf("%d%d%d%d", &n, &x, &y, &s); 102 for(int i = 1; i <= n; ++i) head[i] = -1; tot = 0; 103 for(int i = 1; i <= n; ++i) dis[i] = INF; dis[s] = 0; 104 int u, v, w; 105 for(int i = 1; i <= x; ++i){ 106 scanf("%d%d%d", &u, &v, &w); 107 add(u, v, w); add(v, u, w); 108 mp[u].pb(v); mp[v].pb(u); 109 } 110 111 vector<node > tmp; 112 for(int i = 1; i <= y; ++i){ 113 scanf("%d%d%d", &u, &v, &w); 114 tmp.pb({u, v, w}); 115 mp[u].pb(v); 116 } 117 //图一定是从出发点s开始的，所以从s出发遍历图，无法到达的点，就是无法到达的点 118 //检测这个点是不是有效点 119 check(s); 120 //缩点 121 for(int i = 1; i <= n; ++i){ 122 if(!scc[i] && ok[i]){ 123 ++col; 124 dfs(i); 125 } 126 } 127 //入度统计 128 for(auto x : tmp){ 129 if(ok[x.u] && ok[x.v]){//有效点 130 vp[scc[x.u]].pb(x); 131 ++du[scc[x.v]]; 132 } 133 } 134 top_sort();//拓扑序 135 for(int i = 1; i <= n; ++i){ 136 if(dis[i] == INF) printf("NO PATHn"); 137 else printf("%lldn", dis[i]); 138 } 139 } 140 141 int main(){ 142 143 solve(); 144 145 return 0; 146 } 147 148 /* 149 7 5 3 4 150 1 2 5 151 3 4 5 152 5 6 10 153 5 7 4 154 6 7 105 155 3 5 -100 156 4 6 -100 157 7 2 -100 158 */
