转载自站主的朋友,原文链接: https://ppssjj.blog.luogu.org/wang-lao-liu-zui-tai-liu-xue-xi-bi-ji

---

网络流是个好东西。其实不需要太多的细节理解，因为网络流需要考察的就是建图，其他都是板子。

最大流其实通俗来说就是：一张图里面，有一个源点S，一个汇点T，他们中间有很多个点很多条边。这些边就像是一条条管道，每个管道有自己的流量（flow）。这时，我们把水从源点倒入，请问最多有多少个单位的水可以流到汇点？

这里仅仅介绍一下Dinic算法。能解决最大流的还有EK，更强的有HLPP。

先提个专有名词： 残余网络：将水灌进去余下的空间所组成的剩余空间网络

Dinic算法利用了分层图的思想。
Step1：用Bfs跑残余网络，构造出分层图。
Step2：用Dfs利用分层图灌水。返回流向汇点的流量。
Step3：统计答案。
Step4：重复执行Step1~3，直到构建不出分层图。

这就是Dinic的大致步骤。

給板子：

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;
}

最大流中有许多技巧，比如说黑白图染色,还有拆点。多多做做题，找找套路。

Q.E.D.