Path

　　首先肯定要求最短路，然后如何确定所有的最短路其实有多种方法。

　　1　根据最短路，那么最短路上的边肯定是可以满足$dist[from] + e.cost = dist[to]$。所以可以求一遍后根据这个公式再向网络图中的加边即可。

　　2　可以从源点和汇点分别求最短路，然后根据每条边肯定满足$dist1[e.from] + e.cost + dist2[e.to] = dij$，再加边就行了。

　　确定最短路后，由于是求最小割，直接跑$Dinic$求出最大流就可以了。

1 #include
2
3 using namespace std;
4 #define Min(a, b) ((a)>(b)?(b):(a))
5 #define P pair
6 #define ll long long
7 const ll INF = __LONG_LONG_MAX__;
8 const int maxn = 2e4 + 13;
9 const int maxm = 2e4 + 13;
10 int N, M;
11
12 struct edge
13 {
14 int to, cost;
15 };
16 struct edge2
17 {
18 ll to, cap, rev;
19 };
20 ll dist1[maxn], dist2[maxn];
21 vector G1[maxn], G2[maxn]; //G1正向图，G2反向图
22 vector G[maxn << 2]; 23 24 void addedge(ll from, ll to, ll cap) 25 { 26 G[from].push_back((edge2){to, cap, (ll)G[to].size()}); 27 G[to].push_back((edge2){from, 0, (ll)G[from].size()-1}); 28 } 29 30 void dijkstra() 31 { 32 priority_queue, greater

> pque;
33 pque.push(P(0, 1));
34 fill(dist1, dist1 + N + 2, INF);
35 dist1[1] = 0;
36 while(!pque.empty())
37 {
38 P q = pque.top();
39 pque.pop();
40 int v = q.second;
41 if(dist1[v] < q.first) 42 continue; 43 for(int i = 0; i < G1[v].size(); i++) 44 { 45 edge e = G1[v][i]; 46 if(dist1[v] + e.cost < dist1[e.to]) 47 { 48 dist1[e.to] = dist1[v] + e.cost; 49 pque.push(P(dist1[e.to], e.to)); 50 } 51 } 52 } 53 54 // pque.push(P(0, N)); 55 // fill(dist2, dist2 + N + 2, INF); 56 // dist2[N] = 0; 57 // while(!pque.empty()) 58 // { 59 // P q = pque.top(); 60 // pque.pop(); 61 // int v = q.second; 62 // if(dist2[v] < q.first) 63 // continue; 64 // for(int i = 0; i < G2[v].size(); i++) 65 // { 66 // edge e = G2[v][i]; 67 // if(dist2[v] + e.cost < dist2[e.to]) 68 // { 69 // dist2[e.to] = dist2[v] + e.cost; 70 // pque.push(P(dist2[e.to], e.to)); 71 // } 72 // } 73 // } 74 } 75 76 void getGraph() 77 { 78 dijkstra(); 79 ll Dij = dist1[N]; 80 for(int i = 1; i <= N; i++) 81 { 82 for(int j = 0; j < G1[i].size(); j++) 83 { 84 edge e = G1[i][j]; 85 if(dist1[e.to] - dist1[i] == e.cost) 86 { 87 addedge((ll)i, (ll)e.to, (ll)e.cost); 88 } 89 } 90 } 91 // for(int i = 1; i <= N; i++) 92 // { 93 // for(int j = 0; j < G1[i].size(); j++) 94 // { 95 // edge e = G1[i][j]; 96 // if(dist1[i] + e.cost + dist2[e.to] == Dij) 97 // { 98 // addedge((ll)i, (ll)e.to, (ll)e.cost); 99 // } 100 // } 101 // } 102 } 103 104 ll level[maxn], iter[maxn<<2]; 105 106 void BFS(ll s) 107 { 108 memset(level, -1, sizeof(level)); 109 queue que;
110 que.push(s);
111 level[s] = 0;
112 while(!que.empty())
113 {
114 int v = que.front();
115 que.pop();
116 for(int i = 0; i < G[v].size(); i++) 117 { 118 edge2 e = G[v][i]; 119 if(e.cap > 0 && level[e.to] < 0) 120 { 121 level[e.to] = level[v] + 1; 122 que.push(e.to); 123 } 124 } 125 } 126 } 127 128 ll DFS(ll v, ll t, ll f) 129 { 130 if(v == t) 131 return f; 132 for(ll &i = iter[v]; i < G[v].size(); i++) 133 { 134 edge2 &e = G[v][i]; 135 if(e.cap > 0 && level[v] < level[e.to]) 136 { 137 ll d = DFS(e.to, t, min(f, e.cap)); 138 if(d > 0)
139 {
140 e.cap -= d;
141 G[e.to][e.rev].cap += d;
142 return d;
143 }
144 }
145 }
146 return 0;
147 }
148
149 ll Dinic(ll s, ll t)
150 {
151 ll flow = 0;
152 while(1)
153 {
154 BFS(s);
155 if(level[t] < 0) 156 return flow; 157 memset(iter, 0, sizeof(iter)); 158 ll f = DFS(s, t, INF); 159 while(f > 0)
160 {
161 flow += f;
162 f = DFS(s, t, INF);
163 }
164 }
165 }
166
167 int main()
168 {
169 //freopen("input.txt", "r", stdin);
170 int T;
171 scanf("%d", &T);
172 while(T--)
173 {
174 int from, to, cost;
175 scanf("%d%d", &N, &M);
176 for(int i = 0; i <= N; i++)
177 {
178 G[i].clear();
179 G1[i].clear();
180 G2[i].clear();
181 }
182 for(int i = 0; i < M; i++)
183 {
184 scanf("%d%d%d", &from, &to, &cost);
185 G1[from].push_back( (edge){to, cost});
186 G2[to].push_back( (edge){from, cost});
187 }
188 getGraph();
189 printf("%lld\n", Dinic(1, N));
190 }
191
192 }