无源汇上下界可行流 学习笔记

模板题

通解：

构造一个新图，使得边$(u,v)$的上下界变为$[0,c_R(u,v)-c_L(u,v)]$。

容易证明，这样满足最大流容量限制。

但因为出边，入边数目、容量不同，不满足流量守恒。

也就是对于一个点u，会改变$|c_{in}-c_{out}|$的容量。

设$c_{in}=\sum_{(u,v)\in V}c_L(u,v),c_{out}=\sum_{(v,u)\in V}c_L(v,u)$

换句话说，即如果入流减少的多，会少流$c_{in}-c_{out}$。

反之，会多流$c_{out}-c_{in}$。

为了使其满足可行流的性质，我们可以让$S$与其流一条容量为$c_{in}-c_{out}$的流。

反正，可以使其和汇点流一条为$c_{out}-c_{in}$的流。

这样便满足了流量守恒。

但是注意到，源点和汇点所流的流为补充流，也就是说，在原图中必须流满。

扩大（缩小）新图中的限制，这样才能满足原图上下界。

也就是说从源点向汇点要流一条最大流。

若最大流存在且满流，则原图中的可行流存在。

证明：

对于原图中的任意一条可行流，我们可以通过上述方式唯一构造出一组最大流。

同理，对于新图中的最大流，其满足流量限制。

我们可以给每条边加上流量下界，从而构造原图中的流。

多余的补偿与和S，T的流相抵消。

得证。

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=209,M=(N+10200)*2,INF=0x3f3f3f3f;
int ver[M],nxt[M],f[M],h[N],l[M],tot,S,T;
int n,m,ans,A[N],cur[N],dis[N],Q[N],hh,tt,cnt;

inline void add(int a,int b,int c,int d)
{
    ver[tot]=b,nxt[tot]=h[a],f[tot]=d-c,l[tot]=c,h[a]=tot++;
    ver[tot]=a,nxt[tot]=h[b],f[tot]=0,h[b]=tot++;
}

inline bool BFS()
{
    memset(dis,-1,sizeof dis);
    hh=tt=0;Q[0]=S;
    dis[S]=0;cur[S]=h[S];
    while(hh<=tt)
    {
        int u=Q[hh++];
        for(int i=h[u];~i;i=nxt[i])
        {
            int v=ver[i];
            if(dis[v]==-1&&f[i])
            {
                dis[v]=dis[u]+1;
                Q[++tt]=v;
                cur[v]=h[v];
                if(v==T) return true;
            }
        }
    }
    return false;
}

int dfs(int u,int lim)
{
    if(u==T) return lim;
    int flow=0,delta;
    for(int i=cur[u];~i&&flow<lim;i=nxt[i])
    {
        cur[u]=i;
        int v=ver[i];
        if(dis[v]==dis[u]+1&&f[i])
        {
            delta=dfs(v,min(f[i],lim-flow));
            if(!delta) dis[v]=-1;
            flow+=delta;
            f[i]-=delta;
            f[i^1]+=delta;
        }
    }
    return flow;
}

inline int Dinic()
{
    int res=0;
    while(BFS())
    {
        res+=dfs(S,INF);
    }
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    S=n+1,T=n+2;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
        A[a]-=c,A[b]+=c;
    }
    
    for(int i=1;i<=n;i++) 
        if(A[i]>0) add(S,i,0,A[i]),cnt+=A[i];
        else if(A[i]<0) add(i,T,0,-A[i]);
    
    if(Dinic()<cnt) puts("NO");
    else 
    {
        puts("YES");
        for(int i=0;i<2*m;i+=2)
            printf("%d\n",f[i^1]+l[i]);
    }
    return 0;
}