题意简单的来说就是从1点到n点，最大的流量是多少。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<1 10 #define rson m+1,r,rt<<1|1 11 #define max3(a,b,c) max(a,max(b,c)) 12 #define min3(a,b,c) min(a,min(b,c)) 13 #define _S(X) cout << x << ' '; 14 #define __S(x) cout << x << endl; 15 typedef pair<int,int> pll; 16 const int INF = 0x3f3f3f3f; 17 const LL mod = (int)1e9+7; 18 const int N = 405; 19 int head[N], w[N], to[N], nx[N]; 20 int n, m, _u, _v, _w; 21 int tot, s, t; 22 int deep[N]; 23 void add(int u, int v, int val){ 24 w[tot] = val; 25 to[tot] = v; 26 nx[tot] = head[u]; 27 head[u] = tot++; 28 } 29 30 void init(){ 31 memset(head, -1, sizeof(head)); 32 tot = 0; 33 s = 1; 34 t = n; 35 } 36 37 int bfs(){ 38 queue<int> q; 39 memset(deep, 0, sizeof(deep)); 40 q.push(s); 41 deep[s] = 1; 42 while(!q.empty()){ 43 int u = q.front(); 44 q.pop(); 45 for(int i = head[u]; ~i; i = nx[i]){ 46 if(w[i] > 0 && deep[to[i]] == 0){ 47 deep[to[i]] = deep[u] + 1; 48 q.push(to[i]); 49 } 50 } 51 } 52 if(deep[t] > 0) return 1; 53 return 0; 54 } 55 int Dinic(int u, int flow){ 56 if(u == t) return flow; 57 for(int i = head[u]; ~i; i = nx[i]){ 58 if(deep[u]+1 == deep[to[i]] && w[i] > 0){ 59 int di = Dinic(to[i], min(w[i], flow)); 60 if(di > 0){ 61 w[i] -= di, w[i^1] += di; 62 return di; 63 } 64 } 65 } 66 return 0; 67 } 68 int main(){ 69 while(~scanf("%d%d", &m, &n)){ 70 init(); 71 for(int i = 1; i <= m; i++){ 72 scanf("%d%d%d", &_u, &_v, &_w); 73 add(_u, _v, _w); 74 add(_v, _u, 0); 75 } 76 s = 1; t = n; 77 int ans = 0, tmp; 78 while(bfs()){ 79 while(tmp = Dinic(s, INF)) ans += tmp; 80 } 81 printf("%d ", ans); 82 } 83 return 0; 84 }
Dinic 还可以用当前弧优化，记录了当前处理到那一条边，就不需要重头再遍历那些l边。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<1 10 #define rson m+1,r,rt<<1|1 11 #define max3(a,b,c) max(a,max(b,c)) 12 #define min3(a,b,c) min(a,min(b,c)) 13 #define _S(X) cout << x << ' '; 14 #define __S(x) cout << x << endl; 15 typedef pair<int,int> pll; 16 const int INF = 0x3f3f3f3f; 17 const LL mod = (int)1e9+7; 18 const int N = 405; 19 int head[N], w[N], to[N], nx[N]; 20 int n, m, _u, _v, _w; 21 int tot, s, t; 22 int deep[N], cur[N]; 23 void add(int u, int v, int val){ 24 w[tot] = val; 25 to[tot] = v; 26 nx[tot] = head[u]; 27 head[u] = tot++; 28 } 29 30 void init(){ 31 memset(head, -1, sizeof(head)); 32 tot = 0; 33 s = 1; 34 t = n; 35 } 36 37 int bfs(){ 38 queue<int> q; 39 memset(deep, 0, sizeof(deep)); 40 q.push(s); 41 deep[s] = 1; 42 while(!q.empty()){ 43 int u = q.front(); 44 q.pop(); 45 for(int i = head[u]; ~i; i = nx[i]){ 46 if(w[i] > 0 && deep[to[i]] == 0){ 47 deep[to[i]] = deep[u] + 1; 48 q.push(to[i]); 49 } 50 } 51 } 52 if(deep[t] > 0) return 1; 53 return 0; 54 } 55 int Dinic(int u, int flow){ 56 if(u == t) return flow; 57 for(int &i = cur[u]; ~i; i = nx[i]){ 58 if(deep[u]+1 == deep[to[i]] && w[i] > 0){ 59 int di = Dinic(to[i], min(w[i], flow)); 60 if(di > 0){ 61 w[i] -= di, w[i^1] += di; 62 return di; 63 } 64 } 65 } 66 return 0; 67 } 68 int main(){ 69 while(~scanf("%d%d", &m, &n)){ 70 init(); 71 for(int i = 1; i <= m; i++){ 72 scanf("%d%d%d", &_u, &_v, &_w); 73 add(_u, _v, _w); 74 add(_v, _u, 0); 75 } 76 s = 1; t = n; 77 int ans = 0, tmp; 78 while(bfs()){ 79 for(int i = 1; i <= n; i++) cur[i] = head[i]; 80 while(tmp = Dinic(s, INF)) ans += tmp; 81 } 82 printf("%d ", ans); 83 } 84 return 0; 85 }
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<1 10 #define rson m+1,r,rt<<1|1 11 #define max3(a,b,c) max(a,max(b,c)) 12 #define min3(a,b,c) min(a,min(b,c)) 13 #define _S(X) cout << x << ' '; 14 #define __S(x) cout << x << endl; 15 typedef pair<int,int> pll; 16 const int INF = 0x3f3f3f3f; 17 const LL mod = (int)1e9+7; 18 const int N = 405; 19 int head[N], w[N], to[N], nx[N]; 20 int vis[N], pre[N], id[N]; 21 int n, m, _u, _v, _w; 22 int tot, s, t; 23 void add(int u, int v, int val){ 24 w[tot] = val; 25 to[tot] = v; 26 nx[tot] = head[u]; 27 head[u] = tot++; 28 } 29 30 void init(){ 31 memset(head, -1, sizeof(head)); 32 tot = 0; 33 s = 1; 34 t = n; 35 } 36 37 int bfs(){ 38 queue<int> q; 39 memset(vis, 0, sizeof(vis)); 40 q.push(s); 41 vis[s] = 1; 42 pre[s] = s; 43 while(!q.empty()){ 44 int u = q.front(); 45 q.pop(); 46 for(int i = head[u]; ~i; i = nx[i]){ 47 if(!vis[to[i]] && w[i]){ 48 pre[to[i]] = u; 49 id[to[i]] = i; 50 vis[to[i]] = 1; 51 if(to[i] == t) return true; 52 q.push(to[i]); 53 } 54 } 55 } 56 return false; 57 } 58 int EK(){ 59 int ans = 0; 60 while(bfs()){ 61 int mi = INF; 62 for(int i = t; i != s; i = pre[i]){ 63 mi = min(mi, w[id[i]]); 64 } 65 for(int i = t; i != s; i = pre[i]){ 66 w[id[i]] -= mi; 67 w[id[i]^1] += mi; 68 } 69 ans += mi; 70 } 71 return ans; 72 } 73 int main(){ 74 while(~scanf("%d%d", &m, &n)){ 75 init(); 76 for(int i = 1; i <= m; i++){ 77 scanf("%d%d%d", &_u, &_v, &_w); 78 add(_u, _v, _w); 79 add(_v, _u, 0); 80 } 81 s = 1; t = n; 82 printf("%d ", EK()); 83 } 84 return 0; 85 }