——果断附isap代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 using std::min; 6 7 const int maxn = 200001; 8 9 int n, m, cnt, maxflow, s, t;//s为起点，t为终点 10 int head[maxn], next[maxn], to[maxn], val[maxn], gap[maxn], dis[maxn];//gap记录当前有多少点标号(层号)为k 11 12 inline void add(int x, int y, int z) 13 { 14 to[cnt] = y; 15 val[cnt] += z; 16 next[cnt] = head[x]; 17 head[x] = cnt++; 18 } 19 20 inline int dfs(int u, int flow) 21 { 22 if(u == t) return flow; 23 int ret = flow, i, d;//ret存的是当前搜索的最小flow 24 for(i = head[u]; i != -1; i = next[i]) 25 if(val[i] && dis[u] == dis[to[i]] + 1) 26 { 27 d = dfs(to[i], min(ret, val[i])); 28 val[i] -= d; 29 val[i ^ 1] += d; 30 if(!(ret -= d)) return flow; 31 } 32 if(!--gap[dis[u]]) dis[s] = n; 33 ++gap[++dis[u]]; 34 return flow - ret; 35 } 36 37 int main() 38 { 39 int i, j, x, y, z; 40 memset(head, -1, sizeof(head)); 41 scanf("%d %d %d %d", &n, &m, &s, &t); 42 for(i = 1; i <= m; i++) 43 { 44 scanf("%d %d %d", &x, &y, &z); 45 add(x, y, z); 46 add(y, x, 0); 47 } 48 for(gap[s] = n; dis[s] < n;) maxflow += dfs(s, 1e9); 49 printf("%d", maxflow); 50 return 0; 51 }
其实我还没搞懂，但是感觉代码量好少！
然而——草，垃圾dfs，好多题都被卡，TM不用了！
但是迭代版的isap好像代码量多的一匹，所以我还是学Dinic吧，嗯，就这样。
Dinic代码，有当前弧优化。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 5 using namespace std; 6 7 int n, m, cnt, ans; 8 int head[10001], to[200001], val[200001], next[200001], dis[10001], cur[10001]; 9 10 void add(int x, int y, int z) 11 { 12 to[cnt] = y; 13 val[cnt] += z; 14 next[cnt] = head[x]; 15 head[x] = cnt++; 16 } 17 18 int dfs(int u, int t, int maxflow) 19 { 20 if(u == t) return maxflow; 21 int i, ret = 0, d, v; 22 for(i = cur[u]; i != -1; i = next[i]) 23 { 24 v = to[i]; 25 if(val[i] && dis[v] == dis[u] + 1) 26 { 27 d = dfs(v, t, min(val[i], maxflow - ret)); 28 ret += d; 29 val[i] -= d; 30 val[i ^ 1] += d; 31 cur[u] = i; 32 if(ret == maxflow) return ret; 33 } 34 } 35 return ret; 36 } 37 38 bool bfs(int s, int t) 39 { 40 queue <int> q; 41 memset(dis, -1, sizeof(dis)); 42 q.push(s); 43 dis[s] = 0; 44 int i, u, v; 45 while(!q.empty()) 46 { 47 u = q.front(); 48 q.pop(); 49 for(i = head[u]; i != -1; i = next[i]) 50 { 51 v = to[i]; 52 if(val[i] && dis[v] == -1) 53 { 54 dis[v] = dis[u] + 1; 55 if(v == t) return 1; 56 q.push(v); 57 } 58 } 59 } 60 return 0; 61 } 62 63 int main() 64 { 65 int i, j, s, t, x, y, z; 66 scanf("%d %d %d %d", &n, &m, &s, &t); 67 memset(head, -1, sizeof(head)); 68 for(i = 1; i <= m; i++) 69 { 70 scanf("%d %d %d", &x, &y, &z); 71 add(x, y, z); 72 add(y, x, 0); 73 } 74 //dinic 75 while(bfs(s, t)) 76 { 77 for(i = 1; i <= n; i++) cur[i] = head[i]; 78 ans += dfs(s, t, 1e9); 79 } 80 printf("%d", ans); 81 return 0; 82 }