题意： 给n个点，及m根pipe，每根pipe用来流躺液体的，单向的，每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体，里面流躺物质。
并且满足每根pipe一定的流量限制，范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri(最大流问题)，同时最小不能低于Li。
/* 无源汇的上下界可行流。 参见：周源《一种简易的方法求解流量有上下界的网络中网络流问题》。 */ #include<cstdio> #include<iostream> #include<cstring> #include<queue> #define N 210 #define M 80010 #define inf 1000000000 using namespace std; int head[N],dis[N],low[M],s[N],n,m,cnt,S,T; struct node{int v,f,pre;}e[M]; queue<int> q; void add(int u,int v,int f){ e[++cnt].v=v;e[cnt].f=f;e[cnt].pre=head[u];head[u]=cnt; e[++cnt].v=u;e[cnt].f=0;e[cnt].pre=head[v];head[v]=cnt; } bool bfs(){ memset(dis,-1,sizeof(dis)); q.push(S);dis[S]=0; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].pre) if(e[i].f&&dis[e[i].v]==-1){ dis[e[i].v]=dis[u]+1; q.push(e[i].v); } } return dis[T]!=-1; } int dinic(int x,int f){ int rest=f; if(x==T) return f; for(int i=head[x];i;i=e[i].pre){ if(!e[i].f||dis[e[i].v]!=dis[x]+1) continue; int t=dinic(e[i].v,min(rest,e[i].f)); if(!t) dis[e[i].v]=-1; e[i].f-=t;e[i^1].f+=t;rest-=t; } if(rest==f) dis[x]=-1; return f-rest; } int main(){ int Q;scanf("%d",&Q); while(Q--){ memset(head,0,sizeof(head)); memset(s,0,sizeof(s)); int sum=0;cnt=1; scanf("%d%d",&n,&m);S=0;T=n+1; for(int i=1;i<=m;i++){ int u,v,minn,maxn; scanf("%d%d%d%d",&u,&v,&minn,&maxn); low[i]=minn;s[u]+=minn;s[v]-=minn; add(u,v,maxn-minn); } for(int i=1;i<=n;i++) if(s[i]>0) add(i,T,s[i]),sum+=s[i]; else if(s[i]<0) add(S,i,-s[i]); int maxflow=0; while(bfs()) maxflow+=dinic(S,inf); if(maxflow!=sum) printf("NO "); else { printf("YES "); for(int i=1;i<=m;i++) printf("%d ",low[i]+e[(i<<1)^1].f); } } return 0; }