/* 我也没有读题 刚学就直接搜的这类题 找了个简单的练习 大致上好像是这么个意思 给你一个图 边有上下界 求无源汇最大流 没有输出NO 有则输出 YES 并输出 各边的流量 */ #include<iostream> #include<string.h> using namespace std; const int N=205; struct node { int u,v; }e[N*N]; int l[N][N],u[N][N],g[N][N],d[N],num[N],n,m,sink,src; int min(int a,int b){return a<b?a:b;} int sap(int u,int f) { if(u==sink) return f; int v,mind=n+1,last=f,cost; for(v=0;v<=n+1;++v) { if(g[u][v]>0)//有流量 { if(d[u]==d[v]+1)//有允许边 { cost=sap(v,min(last,g[u][v])); g[u][v]-=cost;//修改图 g[v][u]+=cost; last-=cost;//修改剩余流量 if(d[src]>=n+2)//结束标志 return f-last; if(last==0)//使用完就退出 break; } if(d[v]<mind)//下面更新距离的时候用 求其能连接到的最小距离 这个判断和上边的那个判断并列 因为他们是互斥的,只有当找不到允许边的时候才用得着mind mind=d[v]; } } if(last==f)//流量没有使用 即 没有允许边 { --num[d[u]]; if(num[d[u]]==0)//若出现断层 { d[src]=n+2; } d[u]=mind+1; ++num[d[u]]; } return f-last; } int main() { int t,i,j,a,b,c,h; cin>>t; while(t--) { memset(g,sizeof(g)); memset(l,sizeof(l));//曾经忘了初始化这俩 老是错 memset(u,sizeof(u));// cin>>n>>m; sink=n+1; src=0; for(i=1;i<=m;++i) { cin>>a>>b>>c>>h; e[i].u=a;//记录边 以便 存在答案是输出用 e[i].v=b; l[a][b]=c; u[a][b]=h; } b=0; for(i=1;i<=n;++i) { a=0; for(j=1;j<=n;++j) { a+=l[j][i]-l[i][j];//统计 输入流比输出流多多少 g[i][j]=u[i][j]-l[i][j]; } if(a>0) b+=g[0][i]=a; else g[i][n+1]=-a; } c=0; memset(d,sizeof(d)); memset(num,sizeof(num)); for(num[0]=n+2;d[0]<n+2;) c+=sap(0,0x7fffffff); if(c<b) cout<<"NO"<<endl; else { cout<<"YES"<<endl; for(i=1;i<=m;++i) cout<<(u[e[i].u][e[i].v]-g[e[i].u][e[i].v])<<endl; } } return 0; }