一、题面
二、分析
网络流的裸题。
1 Edmonds-Karp算法
求解网络流其实就是一个不断找增广路，然后每次找到一条增广路后更新残余网络的一个过程。
EK算法主要就是用bfs去找增广路，然后不断更新残余网络得到最终答案。
2 Dinic算法
对于Ford-Fulkerson和Edmonds-Karp算法，求解网络流都是一次次用DFS或者BFS，这其实是很费时的，Dinic相当于就是一次BFS然后DFS求解出多条增广路。
3 ISAP
三、AC代码
1 //Edmonds-Karp 2 #include <cstdio> 3 #include <iostream> 4 #include <vector> 5 #include <queue> 6 #include <cstring> 7 using namespace std; 8 #define ll long long 9 const int maxn = 2e2 + 13; 10 const int INF = 1e8 + 1; 11 int N, M; 12 int Flow[maxn]; //找到的最小的容量 13 int Pre[maxn]; //记录父节点 14 struct edge 15 { 16 //终点、容量、反边 17 int to, cap, rev; 18 }; 19 int G[maxn][maxn]; 20 void add_edge(int from, int to, int cap) 21 { 22 G[from][to] += cap; 23 } 24 25 int BFS(int s, int t) 26 { 27 memset(Pre, -1, sizeof(Pre)); 28 queue<int> Q; 29 Q.push(s); 30 Pre[s] = -1; 31 Flow[s] = INF; 32 while(!Q.empty()) 33 { 34 int q = Q.front(); 35 if(q == t) 36 break; 37 Q.pop(); 38 for(int i = 1; i <= M; i++) 39 { 40 if(i != s && G[q][i] > 0 && Pre[i] == -1) 41 { 42 Pre[i] = q; 43 Flow[i] = min(Flow[q], G[q][i]); 44 Q.push(i); 45 } 46 } 47 } 48 if(Pre[t] == -1) 49 return 0; 50 else 51 return Flow[t]; 52 } 53 54 ll EK(int s, int t) 55 { 56 ll ans = 0; 57 int f = BFS(s, t); 58 while(f) 59 { 60 ans += f; 61 int p = t; 62 while(Pre[p] != -1) 63 { 64 G[Pre[p]][p] -= f; 65 G[p][Pre[p]] += f; 66 p = Pre[p]; 67 } 68 f = BFS(s, t); 69 } 70 return ans; 71 } 72 73 int main() 74 { 75 freopen("input.txt", "r", stdin); 76 while(scanf("%d%d", &N, &M) != EOF) 77 { 78 memset(G, 0, sizeof(G)); 79 int from, to, cap; 80 for(int i = 0; i < N; i++) 81 { 82 scanf("%d%d%d", &from, &to, &cap); 83 add_edge(from, to, cap); 84 } 85 printf("%I64d ", EK(1, M)); 86 } 87 return 0; 88 }
1 //Dinic 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 9 using namespace std; 10 #define ll long long 11 #define Min(a,b) ((a)>(b)?(b):(a)) 12 #define Max(a,b) ((a)>(b)?(a):(b)) 13 const int INF = 1e9; 14 const int maxn = 5e2 + 13; 15 struct edge 16 { 17 int to, cap, rev; 18 }; 19 vector<edge> G[maxn]; 20 int N, M; 21 int level[maxn], iter[maxn]; 22 //iter数组的作用就是记录DFS时该结点已经访问到的邻接点的位置 23 void add_edge(int from, int to, int cap) 24 { 25 G[from].push_back( (edge){to, cap, G[to].size()}); 26 G[to].push_back( (edge){from, 0, G[from].size() - 1}); 27 } 28 29 void BFS(int s) 30 { 31 memset(level, -1, sizeof(level)); 32 queue<int> que; 33 level[s] = 0; 34 que.push(s); 35 while(!que.empty()) 36 { 37 int v = que.front(); 38 que.pop(); 39 for(int i = 0; i < G[v].size(); i++) 40 { 41 edge &e = G[v][i]; 42 if(e.cap > 0 && level[e.to] < 0) 43 { 44 level[e.to] = level[v] + 1; 45 que.push(e.to); 46 } 47 } 48 } 49 } 50 51 int DFS(int s, int t, int f) 52 { 53 if(s == t) 54 return f; 55 for(int &i = iter[s]; i < G[s].size(); i++) 56 { 57 edge &e = G[s][i]; 58 if(e.cap > 0 && level[s] < level[e.to]) 59 { 60 int d = DFS(e.to, t, Min(f, e.cap)); 61 if(d > 0) 62 { 63 e.cap -= d; 64 G[e.to][e.rev].cap += d; 65 return d; 66 } 67 } 68 } 69 return 0; 70 } 71 72 int Dinic(int s, int t) 73 { 74 int flow = 0; 75 while(1) 76 { 77 BFS(s); 78 if(level[t] < 0) 79 return flow; 80 memset(iter, 0, sizeof(iter)); 81 int f = DFS(s, t, INF); 82 while(f > 0) 83 { 84 flow += f; 85 f = DFS(s, t, INF); 86 } 87 } 88 } 89 90 int main() 91 { 92 //freopen("input.txt", "r", stdin); 93 int from, to, cap; 94 while(~scanf("%d%d", &N, &M)) 95 { 96 for(int i = 0; i < N; i++) 97 { 98 scanf("%d%d%d", &from, &to, &cap); 99 add_edge(from, to, cap); 100 } 101 printf("%d ", Dinic(1, M)); 102 for(int i = 1; i < M; i++) 103 { 104 G[i].clear(); 105 } 106 } 107 return 0; 108 }
1 //ISAP 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 9 using namespace std; 10 #define ll long long 11 #define Min(a,b) ((a)>(b)?(b):(a)) 12 #define Max(a,b) ((a)>(b)?(a):(b)) 13 const int INF = 1e9; 14 const int maxn = 2e2 + 13; 15 struct edge{ 16 int v, w, nxt; 17 } e[maxn<<1]; 18 int h[maxn], tot, n, m, gap[maxn], last[maxn], d[maxn],que[maxn], ql, qr; 19 vector<int> inv[maxn]; 20 21 int read() { 22 int x=0,f=1; 23 char c=getchar(); 24 for (;!isdigit(c);c=getchar()) if (c=='-') f=-1; 25 for (;isdigit(c);c=getchar()) x=x*10+c-'0'; 26 return x*f; 27 } 28 29 void add(int u, int v, int w) 30 { 31 e[++tot] = (edge){v, w, h[u]}; 32 h[u] = tot; 33 e[++tot] = (edge){u, 0, h[v]}; 34 h[v] = tot; 35 } 36 37 void init(int s, int t) 38 { 39 memset(gap, 0, sizeof(gap)); 40 memset(d, 0, sizeof(d)); 41 ++gap[d[t] = 1]; 42 for(int i = 1; i <= n; i++) 43 last[i] = h[i]; 44 que[ql = qr = 1] = t; 45 while(ql <= qr) 46 { 47 int x = que[ql++]; 48 for(int i = h[x], v = e[i].v;i; i = e[i].nxt, v = e[i].v) 49 { 50 if(!d[v]) 51 { 52 ++gap[d[v] = d[x] + 1]; 53 que[++qr] = v; 54 } 55 } 56 } 57 } 58 59 int aug(int x, int s, int t, int mi) 60 { 61 if(x == t) 62 return mi; 63 int flow = 0; 64 for(int &i = last[x], v = e[i].v;i;i = e[i].nxt, v = e[i].v) 65 { 66 if(d[x] == d[v] + 1) 67 { 68 int tmp = aug(v, s, t, min(mi, e[i].w)); 69 flow += tmp; 70 mi -= tmp; 71 e[i].w -= tmp; 72 e[i^1].w += tmp; 73 if(!mi) 74 return flow; 75 } 76 } 77 if(!(--gap[d[x]])) 78 d[s] = n + 1; 79 ++gap[++d[x]]; 80 last[x] = h[x]; 81 return flow; 82 } 83 84 int maxflow(int s, int t) 85 { 86 init(s, t); 87 int ret = aug(s, s, t, INF); 88 while(d[s] <= n) 89 ret += aug(s, s, t, INF); 90 return ret; 91 } 92 93 int main() 94 { 95 freopen("input.txt", "r", stdin); 96 while(~scanf("%d%d", &m, &n)) 97 { 98 tot = 1; 99 memset(h, 0, sizeof(h)); 100 for(int i = 1; i <= n; i++) 101 inv[i].clear(); 102 for(int i = 1; i <= m; i++) 103 { 104 int u = read(); 105 int v = read(); 106 int w = read(); 107 add(u, v, w); 108 if(w) 109 inv[v].push_back(u); 110 } 111 int ans = maxflow(1, n); 112 printf("%d ", ans); 113 } 114 return 0; 115 }