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

· · 题解

何为网络流？

给你一个有向图表示水塔到你家的各种水管通流方向，边表示水管一秒内最大能通多少升的水，水管可能交叉相接又分叉，求从水塔到你家一秒内最大能流多少升水。（水速趋近光速哈。

也就是网络图上的通流问题。

注意，这里说的水塔就是源，水龙头就是汇。

好比这张图的最大流量就是 19 (想一想，为什么。

很容易发现，如果我们把自己变成程序(自己想象一下即可，不需要动手实践，开玩笑的)，那么求解最大流量在我眼中就好像是个贪心，只要是能流的管道我直接流就行了，无非是在dfs过程中求一个路径最小值，在路径上所有边上减去这个最小值，一直重复到一滴都没有就行了，我们把还能通流的路称作增广路。

比如上面那张图就会流成这样，这张图也就是残量图，就是当前流剩的图。

对于上面的例子这个思路是显然正确的。

但是如果在水管之间横着插上一个细管，这个做法就可能变的很邪典。

只要你稍微运用大眼观察法，你就能发现显然上图最大流应该是 2 ，可是刚才的的算法跑出来是 1 ，这是怎么一回事呢？不是自来水厂把你当傻子坑，是因为你dfs顺序的问题，导致出现了不太正确的全局解。

那么我们有没有办法让程序发现到这一点然后反悔呢？

根据生活常识你不能向水龙头里吹把水吹回去让水流回流，那么你可能需要一个新的操作，建立反向边，来达到把水吹回去的目的，没错，是真的吹回去了。

还是这个把厕所下水道水管接到厨房饮用水管的图。但是我们建立了反向边

每次流完一条路，正向边流量减了多少，就把对应的反向边流量加多少。

然后把流反向把边当成一种合理的决策，继续dfs。

得出现在的答案是2。

这个做法是正确的。可以粗略的讲解一下：

因为（1，2，3，4）流过之后，（1，3）再流过来，发现（1，2）流着（3，4）这条道路，于是大喊：“明明是我该流的，你为什么这么熟练啊。”嗯，一看就不是什么正经流。

然后（1，3）把水流沿着（3，2）挤回去，把(3,2)这条边复原。

此时（1，3，2）再流过(2，4)，告诉他:“你看你这他喵的不是能流？”，然后(3，4)的流量给了（1，3），（1，2）乖乖地流（2,，4）。

然后最后的结果是（1，3）流（3，4），（3，2）退流，（1，2）流（2，4）， 咱们就当无事发生过，继续dfs求增广路。

总而言之，反向边就相当于给了你程序反悔的机会。

那么如何实现反向边？已知build建边函数用到的计数变量cnt都是连续的，可得反向边的编号就是正向边的编号加一，不妨设cnt初始值是 1 ，那么以第一组正反边为例，正向边编号是 2 ，反向边是 3 ，都可以异或 1 得到彼此。

至此，总结出思路，从源开始，只要是边上残量不为 0 ，我们就流过这条边，然后递归到找到终点为止，顺带在边上减去实际流量。

int dfs(int now,int rem)//rem是残量,也就是从源过来的【水流量】 
{
    if(now==n)return rem;
    int tmp=rem;
    for(int i=head[now];i;i=e[i].next)
    {
        int v=e[i].to;rad[now]=i;
        if(e[i].w)
        {
            int k=min(e[i].w,tmp);//路径上最大流量和边容量中取个较小值 
            int dlt=dfs(v,k);//解出通过这条边可以流走多少流量 
            e[i].w-=dlt;e[i^1].w+=dlt; 
            tmp-=dlt;//分流了 流量减少 
            if(!tmp)break;
        }
    }
    return rem-tmp;//返回实际流了多少流量 
}

基础思路没问题了，让我们用一个极端的例子看一看目前得出的算法低效之处：

对于这张图，如果你的程序采取了（1，2，3，4）流法，那么反向边（3，2）就会变成 1 ,然后若你的程序再采取（1，3，2，4）的流法，（2，3）复原，此时流量为 2 ，如此往复，程序就会在执行 1998 次之后成功得出答案。但是明显我们只需要流 2 次就能得出答案。

这时候我们就需要分层图的思想，借用让重力让“水流只向低处流”的思想。

核心思想就是用bfs处理一遍图，处理出图上每个点的深度后再dfs。

然后dfs每次递归都只能向更深的地方递归，就像水流只能从高山上向低洼的城市中心流动，而不是在“环城路”上重复流动浪费资源。

大概就是这样写，嗯。

bool bfs()//求增广路 
{
    memset(dis,0,sizeof(dis));
    dis[1]=1;
    queue<int>q;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]==0&&e[i].w)//如果这个点还没有被遍历过,且允许通流(增广路的必要条件) 
            dis[v]=dis[u]+1,q.push(v);
        }
    }
    return dis[n]!=0;//能流到终点欤否？ 
}
int dfs(int now,int rem)//rem是残量,也就是从源过来的【水流量】 
{
    if(now==n)return rem;
    int tmp=rem;
    for(int i=head[now];i;i=e[i].next)
    {
        int v=e[i].to;rad[now]=i;
        if(dis[v]==dis[now]+1&&e[i].w)//分层优化
        {
            int k=min(e[i].w,tmp);//路径上最大流量和边容量中取个较小值 
            int dlt=dfs(v,k);//解出通过这条边可以流走多少流量 
            e[i].w-=dlt;e[i^1].w+=dlt;
            tmp-=dlt;//分流了 流量减少 
            if(!tmp)break;
        }
    }
    return rem-tmp;//返回实际流了多少流量 
}

当然，这样优化后的dinic还是不够优秀的。我们需要一个新的优化，当前弧优化。

名字听起来很牛逼，实际上就是一个去除冗余。

比如你看这张图，当你(1，3，4，...，9)求解完之后，实际上可能(4，6)，（4， 7）等边已经不存在增广的可能了，也就是一滴都没有了，那你(1，2，4)再增广过来的时候，很多条路径其实根本不需要遍历，那么我们干脆设置一个rad数组，记录下对于当前这个节点上一次增广到哪条边了，下次直接从rad这条边开始遍历。

bool bfs()//求增广路 
{
    memset(dis,0,sizeof(dis));
    dis[1]=1;
    queue<int>q;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        rad[u]=head[u];//复原当前弧 
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]==0&&e[i].w)//如果这个点还没有被遍历过,且允许通流(增广路的必要条件) 
            dis[v]=dis[u]+1,q.push(v);
        }
    }
    return dis[n]!=0;//能流到终点欤否？ 
}
int dfs(int now,int rem)//rem是残量,也就是从源过来的【水流量】 
{
    if(now==n)return rem;
    int tmp=rem;
    for(int i=rad[now];i;i=e[i].next)//优化:当前弧 
    {
        int v=e[i].to;rad[now]=i;
        if(dis[v]==dis[now]+1&&e[i].w)//优化:分层图 
        {
            int k=min(e[i].w,tmp);//路径上最大流量和边容量中取个较小值 
            int dlt=dfs(v,k);//解出通过这条边可以流走多少流量 
            e[i].w-=dlt;e[i^1].w+=dlt;//优化:反向边 
            tmp-=dlt;//分流了 流量减少 
            if(!tmp)break;
        }
    }
    return rem-tmp;//返回实际流了多少流量 
}

放上标程:(有些简单的步骤比如建边压行较为严重)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
const int maxn=205,maxm=5005;
int n,m,x,s,t,cnt=1;
int head[maxn],rad[maxn],dis[maxn];
struct node
{int next,to,w;}e[maxm*2];
void build(int u,int v,int w)//建边 
{e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;}
inline int read()
{
    int x=0;char r=getchar();
    while(r<'0'||r>'9')r=getchar();
    while(r>='0'&&r<='9')
    {x=x*10+r-'0';r=getchar();}
    return x;
}
void init()
{
    n=read();m=read();s=read(),t=read();
    for(int i=1,x,y,z;i<=m;i++)
    {
        x=read();y=read();z=read();
        build(x,y,z);
        build(y,x,0);//反向边
    }
}
bool bfs()//求增广路 
{
    memset(dis,0,sizeof(dis));
    dis[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        rad[u]=head[u];//复原当前弧 
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(!dis[v]&&e[i].w)//如果这个点还没有被遍历过,且允许通流(增广路的必要条件) 
            dis[v]=dis[u]+1,q.push(v);
        }
    }
    return dis[t]!=0;//能流到终点欤否？ 
}
int dfs(int now,int rem)//rem是残量,也就是从源过来的【水流量】 
{
    if(now==t)return rem;
    int tmp=rem;
    for(int i=rad[now];i;i=e[i].next)//优化:当前弧 
    {
        int v=e[i].to;rad[now]=i;
        if(dis[v]==dis[now]+1&&e[i].w)//优化:分层图 
        {
            int k=min(e[i].w,tmp);//路径上最大流量和边容量中取个较小值 
            int dlt=dfs(v,k);//解出通过这条边可以流走多少流量 
            e[i].w-=dlt;e[i^1].w+=dlt;//优化:反向边 
            tmp-=dlt;//分流了 流量减少 
            if(!tmp)break;
        }
    }
    return rem-tmp;//返回实际流了多少流量 
}
int dicnic()
{
    int ans=0;
    while(bfs())ans+=dfs(s,1e9); 
    return ans;
}
signed main()
{
    init();//读入数据
    int a=dicnic();
    printf("%lld",a);
    return 0;
}