无源汇上下界可行流

%%%liu_runda

前置技能

最大流

定义

上下界网络流流：每条边的流量除了上界还有下界。

无源汇上下界可行流：没有源汇的上下界网络流。因为只需要满足每个点流量守恒，所以一般求可行流。

求解方法

令每条边的流量等于流量下界，得到一个初始流，然后建出这个流的残量网络。

因为初始流的流量不一定守恒，所以我们考虑建一个附加流，使得这个附加流加上初始流之后达到守恒。就像这样：

如果某个点在初始流中满足流量守恒，那么这个点在附加流中也满足流量守恒。

如果某个点在初始流中流入量比流出量多 x x ，那么这个点在附加流中的流出量比流入量少xx

如果某个点在初始流中流入量比流出量少 x x ，那么这个店在附加流中的流出量比流入量多xx。

而实际上，我们只需要建一个源点 ss s s 和汇点 tt t t 。对于第二种情况，连一条 ss−>i s s − > i 的容量为 x x 的边。第三种情况，连一条i−>tti−>tt的容量为 −x − x 的边。如果存在一种可行流使得 ss−>tt s s − > t t 满流，那么说明存在可行流。而满流就是求解最大流。此时原网络中每条边的流量就是下界+这条边的流量。

模板

ZOJ2314

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 205
#define M ((N*(N+1))<<1)
#define F inline
#define inf 0x7fffffff
using namespace std;
struct edge{ int next,to,v,flow; }ed[M];
int n,m,k,t,ss,tt,sum,ans; bool f[N];
int h[N],l[M],cp[N],dis[N],que[N],A[N];
F char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    if (l==r) return EOF; return *l++;
}
F int _read(){
    int x=; char ch=readc();
    while (!isdigit(ch)) ch=readc();
    while (isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=readc();
    return x;
}
F void writec(int x){ if (x>) writec(x/); putchar(x%+); }
F void _write(int x){ writec(x),putchar('\n'); }
//以上为IO优化
F void addedge(int x,int y,int z){
    ed[k]=(edge){h[x],y,z,},h[x]=k++;
    ed[k]=(edge){h[y],x,,},h[y]=k++;
}
F bool bfs(){
    memset(f,false,sizeof(f));
    int r=,w=; dis[ss]=,f[ss]=true,que[]=ss;
    while (r<w)
        for (int x=que[++r],i=h[x],v;~i;i=ed[i].next)
            if (!f[v=ed[i].to]&&ed[i].v>ed[i].flow)
                dis[v]=dis[x]+,f[v]=true,que[++w]=v;
    return f[tt];
}
int dfs(int x,int rem){
    if (x==tt||!rem) return rem; int sum=;
    for (int &i=cp[x];~i;i=ed[i].next)
        if (dis[ed[i].to]==dis[x]+){
            int p=dfs(ed[i].to,min(rem,ed[i].v-ed[i].flow));
            if (p) sum+=p,ed[i].flow+=p,ed[i^].flow-=p,rem-=p;
            if (!rem) break;
        }
    return sum;
}
F int mf(){
    int ans=;
    while (bfs())
        memcpy(cp,h,sizeof(h)),ans+=dfs(ss,inf);
    return ans;
}
//以上为Dinic板子
int main(){
    for (t=_read();t;t--){
        n=_read(),m=_read(),ss=,tt=n+;
        memset(h,-,sizeof(h)),k=sum=;
        memset(A,,sizeof(A));//A[]存的就是x
        for (int i=,x,y,z;i<=m;i++){
            x=_read(),y=_read(),l[i]=_read(),z=_read();
            A[x]-=l[i],A[y]+=l[i],addedge(x,y,z-l[i]);//初始流
        }
        for (int i=;i<=n;i++)//附加流
            if (A[i]>) addedge(ss,i,A[i]),sum+=A[i];
            else if (A[i]<) addedge(i,tt,-A[i]);
        if (mf()!=sum) puts("NO");//是否满流
        else{
            puts("YES");
            for (int i=;i<(m<<);i+=)
                _write(ed[i].flow+l[i/+]);
        }
        if (t>) putchar('\n');
    }
}