在新Blog上食用

写在前面的话

网络流是什么？能干什么？

简而言之，网络流（network-flows） 是一种类比水流的算法，是用在图论上的。
它的应用遍布通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域，可不只能帮你打NOIP或ACM哟~~
它其实一点也不难。

Lead In

我们来看一个经典的问题。
这里有一张图：

有向图的边权表示流量，问：从A到D能流多少过去？

假设不存在水管爆了等特殊情况。

Method

可以发现，这里有一条Fantastic的路径

所以最大值为1？
很遗憾，最大值为2。

因为可以A-B-D + A-C-D = 2。

True Method

引入网络流Dinic算法。
有点类似BFS，但是在跑出一条合法路径时，需要做一件奇怪的事情。
建反向边。
What?
就是这样：

解释一下。
在跑出一条可行路后，反向建边。
同时给正边减掉最终流到终点的值，反边加上最终流到终点的值。
于是就有了上面那张图。

那有什么用呢？
哝↓

于是就有了另一条可以走的边

可以证明，这个算法是正确的。
So , How ?

Prove

其实在我们走B-C的反向边C-B时，相当于把这段流量退了回去。让B点的流量流向D。
这样做的前提是，发现了另一条可以到达C的路径也就是A-C。
可以这么理解，A-C最终接上了C-D，而A-B接上了B-D。

Attention

注意Dinic算***选择包含弧最少的路径来流。

附录

优秀的Dinic代码：

bool Bfs()
{
    while(!q.empty()) q.pop();
    memset(vis,0,sizeof(vis));
    memset(incf,0x3f,sizeof(incf));
    q.push(S);
    vis[S]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=a[i].next)
        {
            if(vis[a[i].to]||!a[i].v) continue;
            incf[a[i].to]=min(incf[x],a[i].v);
            p[a[i].to]=i;
            q.push(a[i].to);
            vis[a[i].to]=1;
            if(a[i].to==T) return 1;
        }
    }
    return 0;
}
void Dfs()
{
    int x=T;
    while(x!=S)
    {
        int i=p[x];
        a[i].v-=incf[T];
        a[i^1].v+=incf[T];
        x=a[i^1].to;
    }
    maxflow+=incf[T];
}

使用：

while(Bfs()) Dfs();