题解：P14578 【模板】无源汇上下界可行流

· · 题解

前言

此文章摘自笔者的学习笔记，旨在使初学者弄懂上下界网络流。

本文的图片出自 B站此博主 的视频，如有侵权，请及时告知。

题目描述

给定有向图 G=(E,V)，每条边的容量有上界 r_i，和下界 l_i，求出是否有一种合法的流的方式使每条边的流量 f_i，满足 l_i\le f_i\le r_i。

解决方案

不妨令图为这样：

首先构造两个图，分别是下界（低保）网络和增量网络。

下界网络的连边方式和原图相同，容量为下界 l_i。

这里给出图片：

不难发现这个图不满足流量守恒定律。没有关系，我们再给出增量网络。

增量网络的连边和原来是一样的，容量是 r_i-l_i。

给出图片：

我们的思路是在下界网络的基础上进行调整，使其满足流量守恒定律，调整的方式就是利用增量网络。

可以举个例子：

对于点 2，流入量为 3，但流出量为 1，所以我们需要看该点是否能在上界的限制下流出 3-1=2 的量。所以我们构建增量网络，可以发现 2 的出边的 \sum (r_i-l_i) 为 2，所以 2 号可以最多多流出 2 的量，可行。按照此逻辑，我们连 S\overset{2}\to 2，在跑最大流的时候查看这条边是否流满了，如果流满了，那么才能满足条件。

同理如果流出量大于流入量，那么就 u\to T。

给出完整的增量网络：

最后跑最大流，查看我们建的辅助边（图中浅蓝色的边）是否都流满了，如果是，那么就有可行流，否则没有。

输出方案

根据上面的分析，如果你都懂了，那么输出方案非常简单，否则，说明你对这样建图的原因还没懂。如果这样，你也许可以从这一步找到灵感。

一句话概括：一条边的实际流量就是在求最大流时这条边的流量加上 l_i。

因为我们在增量网络上找可行流，就是为了填补下界网络流量不守恒的漏洞，如果能填满，那么才合法，所以实际的量就是填补的量与下界之和。

答疑

初学者很可能这样想：既然在下界网络中多流入了 f，那我在增量网络上肯定要向汇点连边，把多流的量导出去啊。

但肯定不是这样的，再重申一下，我们的思路是既然多流入了 f，那么在上界的限制下多流出 f 才可以构造可行流。所以应该从源点连容量为 f 的边，跑最大流看是否可以从该点成功流出 f。

增量网络的作用是找到可行方案使多流入的导出，而不是直接导出多的量，不然就没有意义。

::::info[代码]

#include<cstdio>
#include<queue>
#include<algorithm>
# define inf 1e9
using namespace std;
const int N=2e3+10;
const int M=1e5+10;

struct bian
{
    int data;
    int nex;
    int w;
}e[M];
int s,t;
int head[N],cnt=1;
int deep[N],cur[N];
int in[N],route[M];
queue <int> q;

void read(int &x)
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
}

void add(int x,int y,int z)
{
    e[++cnt].data=y;  e[cnt].nex=head[x];  e[cnt].w=z;  head[x]=cnt;
    e[++cnt].data=x;  e[cnt].nex=head[y];  e[cnt].w=0;  head[y]=cnt;
}

bool bfs()
{
    for(int i=1;i<=t;i++) deep[i]=0;
    deep[s]=1;
    while(!q.empty()) q.pop();
    q.push(s);
    int now;
    while(!q.empty())
    {
        now=q.front();  q.pop();
        for(int i=head[now];i;i=e[i].nex)
        {
            if(!deep[e[i].data]&&e[i].w)
            {
                deep[e[i].data]=deep[now]+1;
                q.push(e[i].data);
                if(e[i].data==t) return true;
            }
        }
    }
    return false;
}

int dfs(int x,int mf)
{
    if(x==t) return mf;
    int sum=0,f;
    for(int i=cur[x];i;i=e[i].nex)
    {
        cur[x]=i;
        if(deep[e[i].data]==deep[x]+1&&e[i].w)
        {
            f=dfs(e[i].data,min(mf,e[i].w));
            e[i].w-=f;  e[i^1].w+=f;
            sum+=f;  mf-=f;
            if(!mf) break;
        }
    }
    if(!sum) deep[x]=0;
    return sum;
}

int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=1;i<=t;i++) cur[i]=head[i];
        ans+=dfs(s,inf);
    }
    return ans;
}

int main()
{
    int n,m,x,y,l,r,sum=0,ans;
    read(n);  read(m);
    s=n+1;  t=s+1;
    for(int i=1;i<=m;i++)
    {
        read(x);  read(y);  read(l);  read(r);
        add(x,y,r-l);
        route[i]=l;
        in[y]+=l;  in[x]-=l;
    }
    for(int i=1;i<=n;i++)
    {
        if(in[i]>0) add(s,i,in[i]),sum+=in[i];
        else if(in[i]<0) add(i,t,-in[i]);
    }
    ans=dinic();
    if(ans!=sum)
    {
        puts("No");
        return 0;
    }
    puts("Yes");
    for(int i=1;i<=m;i++) printf("%d\n",route[i]+e[i<<1|1].w);
    return 0;
}

::::