ZJU2314(Reactor Cooling)求没有源点和汇点的流量有上下界的可行流
/******************************************题目大意：给出一个流量有上下界的容量网络,没有源点和汇点;求出满足流量平衡条件的可行流;算法思想：构建伴随网络G2:(1)增加附加源点s和附加汇点t;对于每一个点统计流入的总下限sum1,和流出的总下限sum2;求出sum1-sum2,如果大于0则与源点相连,容量为sum1-sum2;如果小于0,则与汇点相连,容量为差的sum2-sum1;(2)保留原网络G1中的每条弧,弧的容量改为c-b;求出伴随网络的最大流f;如果最大流中从附加源点s流出的所有弧均满载,则原网络中存在可行流;否则原网络不存在可行流;如果原网络存在可行流,每条弧的流量为伴随网络中该条弧的流量加上原网络该条弧的流量下界;*******************************************/#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<cstdlib>#include<algorithm>#include<queue>using namespace std;const int MAXN=210;const int INF=0xffffff;//顶点之间不存在弧连接时设置的流量上界struct arc{ int b,c,f;//弧流量的下界，上界和实际流量 int num;//弧的序号};arc G1[MAXN][MAXN];//原网络arc G2[MAXN][MAXN];//伴随网络int n,m;int flag[MAXN];//顶点状态： -1未标号，0已标号未检查，1已标号已检查int pre[MAXN];//标号的第一个分量，表示从哪一个顶点得到int a[MAXN];//标号的第二个分量，表示可改进量aint q;//从队列取出的头元素int cmp(const void*x1,const void *x2){ return ((arc*)x1)->num-((arc*)x2)->num;}//求最大流的基础算法int Ford_Fulkerson(arc G[][MAXN],int s,int t){ while(1)//标号至不可再改进路 { queue<int>Q; memset(flag,-1,sizeof(flag)); memset(pre,-1,sizeof(pre)); memset(a,-1,sizeof(a)); flag[s]=pre[s]=0; a[s]=INF; Q.push(s); while(!Q.empty()&&flag[t]==-1) { q=Q.front(); Q.pop(); for(int i=s; i<=t; i++) { if(flag[i]==-1) { if(G[q][i].c<INF&&G[q][i].f<G[q][i].c)//正向且流量还可以增加 { flag[i]=0; pre[i]=q; a[i]=min(a[q],G[q][i].c-G[q][i].f); Q.push(i); } else if(G[i][q].c<INF&&G[i][q].f>G[i][q].b)//反向且流量还可以减少 { flag[i]=0; pre[i]=-q; a[i]=min(a[q],G[i][q].f-G[i][q].b); Q.push(i); } } } flag[q]=1;//顶点q已标号已检查 } if(flag[t]==-1||a[t]==0)//当汇点没有获得标号或者汇点的调整量为0.则退出 break; int k1=t; int k2=abs(pre[k1]); int a1=a[t];//可改进量 while(1) { if(G[k2][k1].f<INF)//正向 G[k2][k1].f=G[k2][k1].f+a1; else//反向 G[k1][k2].f=G[k1][k2].f-a1; if(k2==s)//调整到源点 break; k1=k2; k2=abs(pre[k2]); } }//算法结束 int max_f=0; for(int i=s; i<=t; i++) { for(int j=s; j<=t; j++) { if(i==s&&G[i][j].f<INF)//源点流出 max_f+=G[i][j].f; if(i==s&&G[j][i].f<INF)//源点流入 max_f-=G[j][i].f; } } // cout<<"max_f=="<<max_f<<endl; return max_f;}//构造伴随矩阵，求可行流int accompany(){ memcpy(G2,G1,sizeof(G1)); int sum1,sum2; for(int i=1; i<=n; i++) { sum1=sum2=0; for(int j=1; j<=n; j++) //统计顶点i发出的弧和进入到顶点i的弧 { if(G2[i][j].b!=INF) sum1+=G2[i][j].b; if(G2[j][i].b!=INF) sum2+=G2[j][i].b; } if(sum2>sum1) { G2[0][i].c=sum2-sum1; G2[0][i].b=G2[0][i].f=0; } else { G2[i][n+1].c=sum1-sum2; G2[i][n+1].b=G2[i][n+1].f=0; } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(G2[i][j].c!=INF)//修改原网络中的弧 { G2[i][j].c=G2[i][j].c-G2[i][j].b; G2[i][j].b=0; } } } Ford_Fulkerson(G2,0,n+1);//求伴随网络的最大流 bool judge=1;//判断是否存在可行流 for(int i=0; i<=n+1; i++) { //cout<<"G2[0]["<<i<<"].f=="<<G2[0][i].f<<" "<<"G2[0]["<<i<<"].c=="<<G2[0][i].c<<endl; if(G2[0][i].c!=INF&&G2[0][i].f!=G2[0][i].c) judge=0; } if(judge==0)//没有可行流 { puts("NO"); return 0; } for(int i=1; i<=n; i++) //修改原网络的弧 { for(int j=1; j<=n; j++) { if(G1[i][j].c!=INF) G1[i][j].f=G2[i][j].f+G1[i][j].b; } } puts("YES"); qsort(G1,MAXN*MAXN,sizeof(G1[0][0]),cmp); for(int i=0; i<m; i++) { printf("%d\n",G1[i/m][i%m].f); }}int main(){ //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0; i<MAXN; i++) { for(int j=0; j<MAXN; j++) G1[i][j].b=G1[i][j].c=G1[i][j].f=G1[i][j].num=INF; } for(int i=1; i<=m; i++) { int u,v,b,c; scanf("%d%d%d%d",&u,&v,&b,&c); G1[u][v].b=b; G1[u][v].c=c; G1[u][v].f=0; G1[u][v].num=i; } accompany(); printf("\n"); } return 0;}