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 */
