上下界网络流

网络流

有三种上下界网络流(最大流)
无源汇可行流/有源汇最大流/有源汇最小流

无源汇可行流

图片出自zsq--CSDN

原图

把下界抽出来

连接到超级原点x，超级汇点y；想像一条不限上界的(y, x)，用必要弧将它们“串”起来，即对于有向必要弧(u, v)，添加(u, y)，(x, v)，容量为必要弧容量。这样就建立了一个等价的网络。 

一个无源汇网络的可行流的方案一定是必要弧是满的。若去掉(y, x)后，附加源x到附加汇y的最大流，能使得x的出弧或者y的入弧都满，充要于原图有可行流。 

1. 按上述方法构造新网络(分离必要弧，附加源汇)
2. 求附加源x到附加汇y的最大流
3. 若x的出弧或y的入弧都满，则有解，将必要弧合并回原图；否则，无解

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define MAXN 205
#define MAXE 30000
#define INF 0x7fffffff
using namespace std;
int start,end;
struct E{
    int next,to,val,id;
}edge[MAXE];
int edge_num=1,head[MAXN];
int n,m,flow;
int Node_flow[MAXN],ans[MAXE];
int depth[MAXN],iter[MAXN],down[MAXE];
queue<int> que;
int EE;
void addedge(int x,int y,int v,int z){
    edge[++edge_num].next=head[x];
    edge[edge_num].to=y;
    edge[edge_num].id=z;
    edge[edge_num].val=v;
    head[x]=edge_num;
}
void BFS(){
    memset(depth,-1,sizeof(depth));
    depth[n+1]=1;
    que.push(n+1);
    while(!que.empty()){
        int fro=que.front();que.pop();
        int i;
        for(i=head[fro];i;i=edge[i].next){
            if(edge[i].val>0 && depth[edge[i].to]==-1){
                depth[edge[i].to]=depth[fro]+1;
                que.push(edge[i].to);
            }
        }
    }
}
int DFS(int x,int flow){
    if(x==end)
        return flow;
    for(int &i=iter[x];i;i=edge[i].next){
        if(depth[edge[i].to]==depth[x]+1 && edge[i].val>0){
            int tmp=DFS(edge[i].to,min(edge[i].val,flow));
            if(tmp>0){
                edge[i].val-=tmp;
                edge[i^1].val+=tmp;
                return tmp;
            }
        }
    }
    return 0;
}
void Dinic(){
    while(true){
        BFS();
        if(depth[end]==-1)break;
        for(int i=1;i<=n+2;i++)
            iter[i]=head[i];
        while(DFS(start,INF));
    }
}
void solve(){
    Dinic();
    bool pd=true;
    int i;
    for(i=head[start];i;i=edge[i].next){
        if (edge[i].val>0){
            pd=false;break;
        }
    }
    if(!pd){printf("NO\n");return;}
    printf("YES\n");
    for(i=1;i<=EE;i++)
        ans[edge[i].id]=edge[i^1].val;
    for(i=1;i<=m;i++)
        printf("%d\n",ans[i]+down[i]);
}
int main(){
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
    scanf("%d%d",&n,&m);
    start=n+1;end=n+2;
    int i;
    for(i=1;i<=m;i++){
        int x,y,a,b;
        scanf("%d%d%d%d",&x,&y,&a,&b);
        addedge(x,y,b-a,i);
        addedge(y,x,0,0);
        Node_flow[y]+=a;
        Node_flow[x]-=a;
        down[i]=a;
    }
    EE=edge_num;
    for(i=1;i<=n;i++){
        if(Node_flow[i]>0){
            addedge(start,i,Node_flow[i],0);addedge(i,start,0,0);
        }
        if(Node_flow[i]<0){
            addedge(end,i,0,0);addedge(i,end,-Node_flow[i],0);
        }
    }
    solve();
    return 0;
}