無源彙上下界可行流

%%%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');
    }
}