网络流——最大流学习笔记

网络流是个好东西。其实不需要太多的细节理解，因为网络流需要考察的就是建图，其他都是板子。 最大流其实通俗来说就是：一张图里面，有一个源点S，一个汇点T，他们中间有很多个点很多条边。这些边就像是一条条管道，每个管道有自己的流量（flow）。这时，我们把水从源点倒入，请问最多有多少个单位的水可以流到汇点？ 这里仅仅介绍一下Dinic算法。能解决最大流的还有EK，更强的有HLPP。 先提个专有名词： 残余网络：将水灌进去余下的空间所组成的剩余空间网络 Dinic算法利用了分层图的思想。 Step1：用Bfs跑残余网络，构造出分层图。 Step2：用Dfs利用分层图灌水。返回流向汇点的流量。 Step3：统计答案。 Step4：重复执行Step1~3，直到构建不出分层图。 这就是Dinic的大致步骤。 給板子： ```cpp bool Bfs() { memset(dep, 0, sizeof dep); dep[q[l = r = 1] = S] = 1; for (;l <= r; l++) for (int i = last[q[l]];i;i = g[i].nxt) if (g[i].flow && !dep[g[i].to]) dep[q[ ++r] = g[i].to] = dep[q[l]] + 1; return dep[T]; } int Dfs(int x,int flow) { if (x == T) return flow; int now = 0; for (int i = last[x];i;i = g[i].nxt) if (dep[g[i].to] == dep[x] + 1 && g[i].flow) { int tmp = Dfs(g[i].to, min(flow, g[i].flow)); g[i].flow -= tmp, g[i ^ 1].flow += tmp; now += tmp, flow -= tmp; if (flow == 0) return now; } if (now == 0) dep[x] = 0; return now; } int Dinic() { int sum = 0; while (Bfs()) sum += Dfs(S, INF); return sum; } ``` 最大流中有许多技巧，比如说黑白图染色（[JZOJ1144圈地计划](https://jzoj.net/senior/#main/show/1144)[JZOJ1919happiness](https://jzoj.net/senior/#main/show/1919)）还有拆点。多多做做题，找找套路。