这两天学习了网络流，故写点东西加深理解。

关于网络流定义证明之类，前人之述备矣，此处整理一些比较舒适的代码实现。

EK

全名是 Edmonds-Karp.

慢但是码量少一些，让人十分欢乐。

EK不需要两次搜索也不需要分层。

更欢乐的是能用EK过的数据范围都较小。这是因为算法的时间复杂度 \(O(VE^2)\) 决定了数据上界。因此存图使用邻接矩阵就行了。

例题P2472 【SCOI2007】 蜥蜴

思路：此题关键在于建图。因为每一个点有容量限制，难以维护，我们不妨把点转化为边，一个入点一个出点，其中连线即为“点的容量”，入边接入点，出边接出点。

因此建图为：

• 连接源点 \(S\) 和所有有蜥蜴的柱子的入点，容量为1（因为只有一只蜥蜴）；
• 连接所有柱子的格子的入点和出点，容量为柱子的高度；
• 连接所有蜥蜴可以跳过的柱子的入点和出点，容量为 \(\inf\) ;
• 连接所有可以跳到边界外的柱子的出点到 \(T\)，容量仍然是\(\inf\).

读者如果仔细思考以上的连法的实际意义便可以很快理解。很多网络流题目考察的就是将复杂的题目要求抽象成图并建立模型的能力。

#include <iostream>
#include <cstring>
#include <queue>
using namespace  std;

int map[22][22];
int lzd[22][22];
int r[1000][1000];
int n,m,s,t,ct;
int d;

int pre[1000];//用以存储增广路
int vis[1000];

int BFS()
{
    memset(pre,0,sizeof(pre));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    
    vis[s]=1;
    pre[s]=s;
    q.push(s);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int v = 1; v <= t; v++)
        {
            if(r[u][v]>0&&!vis[v])//与Dinic同理，如果尚有残量且没去过
            {
                vis[v]=1;
                pre[v]=u;
                if(v==t)return 1;//找到了汇点，这是一条增广路，结束
                q.push(v);
            }
        }
    }
    return 0;
}
int EK()
{
    int ans, d;
    ans=0;
    while(BFS())
    {
        d=1145141919;
        for(int i = t; i != s; i = pre[i])
        {
            d=min(d,r[pre[i]][i]);//找到这条增广路的“瓶颈”即最小容量，即这条增广路对总流量的贡献
        }
        for(int i = t; i != s; i = pre[i])
        {
            //给增广路上所有边和反边更新残量
            r[pre[i]][i]-=d;
            r[i][pre[i]]+=d;
        }
        ans+=d;

    }
    return ans;
}
int main()
{
    cin >> n >> m >> d;
    cin.get();cin.get();
    for(int i = 1; i<=n;i++)
    {
        for(int j = 1; j <= m; j++)
        {
            char tmp=cin.get();
            map[i][j]=tmp-'0';
        }
        cin.get();cin.get();
    }
    for(int i = 1; i<=n;i++)
    {
        for(int j = 1; j <= m; j++)
        {
            char tmp=cin.get();
            lzd[i][j]=(tmp=='.')?0:1;
            if(lzd[i][j])ct++;
        }
        cin.get();cin.get();
    }//输入真恶心，要cin.get()两遍才能吃掉回车符，天啊
    
    //以下建图思路如上，顺序可能不同。
    //超级源点下标当然是1啊（各种方便反正）
    //对于所有柱子，入点的下标为1+(i-1)*m+j, 如果你从左往右从上往下一个个数格子的话那么这就是编号+1。出点的下标为1+(i-1)*m+j+m*n,正好加上一个图的面积。
    //超级汇点直接2*m*n+2，即超级源点+两个面积（出入点）+1
    s=1;
    t=2+n*m*2;
    for(int i = 1; i<=n;i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(lzd[i][j])r[s][1+(i-1)*m+j]=1;
        }
    }
    for(int i = 1; i<=n;i++)
    {
        for(int j = 1; j <= m; j++)
        {
            r[1+(i-1)*m+j][1+(i-1)*m+n*m+j]=map[i][j];
        }
    }
    for(int i = 1; i<=n;i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(map[i][j])
                if(j<=d||j>=m+1-d||i<=d||i>=n+1-d)
                    r[1+(i-1)*m+m*n+j][t]=1145141919;
        }
    }
    for(int i1 = 1; i1<=n;i1++)
    {
        for(int j1 = 1; j1 <= m; j1++)
        {
            for(int i2 = 1; i2<=n;i2++)
            {
                for(int j2 = 1; j2 <= m; j2++)
                {
                    if(i1==i2&&j1==j2)continue;//一样的话就没必要连上了

                    if((i1-i2)*(i1-i2)+(j1-j2)*(j1-j2)<=d*d)//省去开方的一种毕达哥拉斯定理优化形式，实在是太方便了啊
                    {
                        r[1+n*m+(i2-1)*m+j2][1+(i1-1)*m+j1]=1145141919;
                        r[1+n*m+(i1-1)*m+j1][1+(i2-1)*m+j2]=1145141919;
                    }
                }
            }
        }
    }
    cout << ct-EK();//输出不能逃出的，所以记得要用ct减去最大流量啊
}

Dinic

这个算法原本是叫做 Dinitz 的，但是由于 Shimon Even 教授的口误，长期以 Dinic 的名字流传。

比起 EK 在稠密图上快一些,时间复杂度 \(O(V^2 E)\). 适用范围可能更广。

例题P3376 【模板】网络最大流

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int n,m,s,t,tot;

struct edge{
    int b;
    int next;
    long long w;
}e[11000];//有反向边，所以一定要两倍开数组啊
int head[210];
void add(int a, int b, long long w)
{
    e[++tot].b=b;
    e[tot].next=head[a];
    e[tot].w=w;
    head[a]=tot;
}//普通的前向星

int d[210];
int cur[210];//当前弧优化

int BFS()
{
    memset(d,0,sizeof(d));
    memset(cur,0,sizeof(cur));
    queue<int> q;
    
    q.push(s);
    d[s]=1;
    cur[s]=head[s];

    while(q.size())
    {
        int u=q.front();q.pop();
        int v;
        long long w;//不开longlong见祖宗
        for(int i = head[u]; i; i=e[i].next)
        {
            v=e[i].b;
            w=e[i].w;
            if(d[v]==0&&w>0)//d[v]=0时说明未被访问过，此时充当类似vis[]作用
            {
                q.push(v);
                d[v]=d[u]+1;//向前更新
                cur[v]=head[v];//初始化
            }
        }
    }
    if(d[t]==0)return 0;//说明d[t]未被访问，找不到增广路了
    else return 1;
}

long long DFS(int u, long long r)
{
    int v;
    if(u==t)return r;
    for(int i = cur[u]; i; i=e[i].next)//当前弧优化，再次dfs到此时就可以知道上次完成了哪些分支的dfs并清除了其残量
    {
        cur[u]=i;
        int v=e[i].b;
        long long w=e[i].w;
        if((d[v]==d[u]+1)&&w!=0)//确认v在下一层并且有残量
        {
            long long rr=DFS(v,min(r,w));
            if(rr>0)
            {
                e[i].w-=rr;
                e[i^1].w+=rr;
                return rr;
            }
        }
    }
    return 0;
}

long long DINIC()
{
    long long ans=0;
    while(BFS())
    {
        while(long long d=DFS(s,1145141919810))ans+=d;//'='号返回赋值的内容,可以顺便放进while()里面
    }
    return ans;
}

int main()
{
    cin >> n >> m >> s >> t;
    tot=1;//重要。解释见下。
    
    for(int i = 1; i <= m; i++)
    {
        int u ,v;
        long long w;
        cin >> u >> v >> w;
        add(u,v,w);
        add(v,u,0);//建反边。反边的容量是0而不是-w，这在一些情况下可以输出正确结果（？）但是另一些情况下会死循环。
        //因为开始tot=1, 所以开始的一些正反边对下标为(2,3),(4,5)等，正好可以按位异或1相互得到。
    }

    cout << DINIC();
}

解释1：为了在代码实现中方便地得到反边(使用链式前向星时)，由按位异或的性质可以快速得到反边的下标，表示为

\(\forall x \in N\),
\((2x+1) \operatorname{xor} 1=2x\),
且 $ 2x \operatorname{xor} 1=2x+1$