@zzzc18
2017-05-13T08:25:35.000000Z
字数 2056
阅读 1077
网络流
有三种上下界网络流(最大流)
无源汇可行流/有源汇最大流/有源汇最小流
图片出自zsq--CSDN
原图
把下界抽出来
连接到超级原点x,超级汇点y;想像一条不限上界的(y, x),用必要弧将它们“串”起来,即对于有向必要弧(u, v),添加(u, y),(x, v),容量为必要弧容量。这样就建立了一个等价的网络。
一个无源汇网络的可行流的方案一定是必要弧是满的。若去掉(y, x)后,附加源x到附加汇y的最大流,能使得x的出弧或者y的入弧都满,充要于原图有可行流。
- 按上述方法构造新网络(分离必要弧,附加源汇)
- 求附加源x到附加汇y的最大流
- 若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;
}