#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> using namespace std; int s;int e; const int INF=0xfffffff; int Min(int a,int b) { return a>b?b:a; } const int maxn=444; int du[maxn]; int Map[maxn][maxn]; int Map1[maxn][maxn]; int level[maxn]; bool bfs() { queue<int > q;q.push(s); memset(level,0,sizeof(level));level[s]=1; while(!q.empty()){ int cur=q.front(); q.pop(); for(int i=s;i<=e;i++){ if(Map[cur][i]&&!level[i]){ level[i]=level[cur]+1; q.push(i); } } } return level[e]; } int dfs(int x,int val) { int sum=0; if(x==e) return val; for(int i=s;val&&i<=e;i++){ if(Map[x][i]&&level[i]==level[x]+1){ int t=dfs(i,Min(val,Map[x][i])); Map[x][i]-=t;Map[i][x]+=t; val-=t;sum+=t; } } if(sum==0) level[x]=-1; return sum; } int dinic() { for(int i=0;i<=e;i++) for(int j=0;j<=e;j++) Map[i][j]=Map1[i][j]; int ans=0;int t; while(bfs()){ while(t=dfs(s,INF)) ans+=t; } return ans; } int l[1111111]; int a[1111111];int b[1111111]; int main() { int Icase;int n;int m; int c;int d; scanf("%d",&Icase); while(Icase--){ scanf("%d%d",&n,&m); s=0;e=n+1; for(int i=0;i<=e;i++) du[i]=0; for(int i=0;i<=e;i++) for(int j=0;j<=e;j++) Map1[i][j]=0; int sum=0; for(int i=0;i<m;i++){ scanf("%d%d",&a[i],&b[i]);scanf("%d",&c);scanf("%d",&d); du[a[i]]-=c;du[b[i]]+=c; Map1[a[i]][b[i]]=d-c; l[i]=c; } for(int i=1;i<=n;i++){ if(du[i]<0) Map1[i][e]=-du[i]; if(du[i]>0) Map1[s][i]=du[i]; } int ans=dinic(); // cout<<ans<<endl;system("pause"); int flag=0; for(int i=0;i<=e;i++) if(Map[s][i]){flag=1;break;} if(!flag){ printf("YES "); for(int i=0;i<m;i++){ cout<<Map1[a[i]][b[i]]-Map[a[i]][b[i]]+l[i]<<endl; } } else cout<<"NO"<<endl; } return 0; }
du[i]=所有入边下界和-所有出边下界和 设源点s，汇点e
如果du[i]<0 , i->e=-du[i] 流出的流量减少的多 就补全一条边
如果du[i]>0, s->=du[i] 流入的流量减少的多 也补全一条边