【模板】网络最大流

——果断附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 19 20 inline int dfs(int u, int flow) 21 32 if(!gap[dis[u]]) dis[s] = n; 33 ++gap[++dis[u]]; 34 return flow ret; 35 } 36 37 int main() 38 48 for(gap[s] = n; dis[s] < n;) maxflow += dfs(s, 1e9); 49 printf("%d", maxflow); 50 return 0; 51 }
Isap

其实我还没搞懂，但是感觉代码量好少！

然而——草，垃圾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 17 18 int dfs(int u, int t, int maxflow) 19 34 } 35 return ret; 36 } 37 38 bool bfs(int s, int t) 39 58 } 59 } 60 return 0; 61 } 62 int main() 64 74 //dinic 75 while(bfs(s, t)) 76 80 printf("%d", ans); 81 return 0; 82 }
Dinic

上一篇：【模板】二分图最大权完美匹配KM算法

下一篇：运动员最佳匹配问题（km算法）

---

最大流 模板