INnovate's Blog

INnovate's Blog

星际玩家哭了

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

posted on 2019-05-11 08:14:18 | under 学习笔记 |

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

最大流其实通俗来说就是:一张图里面,有一个源点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;
}

最大流中有许多技巧,比如说黑白图染色(JZOJ1144圈地计划JZOJ1919happiness)还有拆点。多多做做题,找找套路。