最大流-dinic算法

dinic与EK算法的比较：

1、使用了层次网络，减小了寻找增广路的代价。

2、允许一次dfs多次增广，一次dfs可以把本层级网络的所有增广路都找出来。

算法步骤：

（1）构建残余网络。

（2）构建层次网络。即初始化距离标号level。距离标号是指定点距离源点边数的最小值。

（3）dfs多路增广。这里找到一条增广路之后，一直回退直到一个顶点v扣除增广流量后还有残余流量，沿途更新边的残余容量。注意到第一次返回到v时，v之前的边的容量并没有更新。直到从v点出发的所有增广路都找完了，才会向前返回并更新边的容量，这时更新值为从v点出发的所有增广路的总流量。相当于将流量积攒下来一起扣除。

（4）重复步骤（2）（3）。

题目链接：Drainage Ditches

自己整了一份比较简洁的模板

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define inf 1<<29
int n,m;
int G[205][205];//残余网络
int level[205];//层级网络，各点的层级
int bfs(int s,int t)//构建层级网络
{
        memset(level,0,sizeof level);
        level[s]=1;
        queue<int> q;
        q.push(s);
        while(!q.empty())
        {
                int top=q.front(); q.pop();
                for(int i=1;i<=n;i++)
                if(!level[i] && G[top][i])//如果这个点没有被搜过，并且top->i这条边的残余容量大于0
                {
                        level[i]=level[top]+1;//将这个点的层级赋为上个点层级+1
                        q.push(i);//将这个点入队
                }
        }
        return level[t];//如果本层级网络能够到达终点
}
int dfs(int v,int t,int flow)//v为当前结点，t为终点，flow为v点存留的流量
{
        int s=flow,increase;//s记录源点的流量，也就是INF，increase为本条增广路的流量
        if(v==t) return flow;//如果搜到了终点，则返回flow，此时flow=increase
        for(int i=1;i<=n;i++)
        {
                if(G[v][i] && level[i]==level[v]+1)//如果v->i这条边残余容量>0，并且i为v的下一个层级
                {
                        increase=dfs(i,t,min(flow,G[v][i]));
                        G[v][i]-=increase;//更新残余网络
                        G[i][v]+=increase;
                        flow-=increase;//v点的残余容量减去增广消耗的流量
                }
        }
        return s-flow;//源点原容量（inf）-源点剩余容量（flow）=本层次网络增广的总流量
}
int dinic(int s,int t)
{
        int maxflow=0,f;
        while(bfs(s,t)) maxflow+=dfs(s,t,inf);//每次尝试构建层次网络，如果构建成功，maxflow加上本网络增广总流量
        return maxflow;
}
int main()
{
        while(~scanf("%d%d",&m,&n))
        {
                memset(G,0,sizeof G);
                int ui,vi,wi;
                for(int i=0;i<m;i++)
                {
                        scanf("%d%d%d",&ui,&vi,&wi);
                        G[ui][vi]+=wi;
                }
                printf("%d\n",dinic(1,n));
        }
        return 0;
}

秒客网

最大流-dinic算法

相关文章