题意： 给n个点，及m根pipe，每根pipe用来流躺液体的，单向的，每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体，里面流躺物质。 并且满足每根pipe一定
题意：
给n个点，及m根pipe，每根pipe用来流躺液体的，单向的，每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体，里面流躺物质。
并且满足每根pipe一定的流量限制，范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri(最大流问题)，同时最小不能低于Li。
题解：
上界用ci表示，下界用bi表示。
下界是必须流满的，那么对于每一条边，去掉下界后，其自由流为ci– bi。
主要思想：每一个点流进来的流=流出去的流
对于每一个点i，令
Mi= sum(i点所有流进来的下界流)– sum(i点所有流出去的下界流)
如果Mi大于0，代表此点必须还要流出去Mi的自由流，那么我们从源点连一条Mi的边到该点。
如果Mi小于0，代表此点必须还要流进来Mi的自由流，那么我们从该点连一条Mi的边到汇点。
如果求S->T的最大流，看是否满流(S的相邻边都流满)。
满流则有解，否则无解。
CODE:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define inf 0x7fffffff 5 #define T 201 6 using namespace std; 7 inline int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 11 while(ch>=‘0‘&&ch<=‘9‘){x*=10;x+=ch-‘0‘;ch=getchar();} 12 return x*f; 13 } 14 int n,m,cnt; 15 int head[205],cur[205],h[205],q[205],in[205]; 16 int low[100005]; 17 struct data{int to,next,v;}e[100005]; 18 void ins(int u,int v,int w) 19 {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;} 20 void insert(int u,int v,int w) 21 {ins(u,v,w);ins(v,u,0);} 22 bool bfs() 23 { 24 for(int i=1;i<=T;i++)h[i]=-1; 25 int t=0,w=1;q[0]=0;h[0]=0; 26 while(t!=w) 27 { 28 int now=q[t];t++; 29 for(int i=head[now];i;i=e[i].next) 30 if(e[i].v&&h[e[i].to]==-1) 31 { 32 h[e[i].to]=h[now]+1; 33 q[w++]=e[i].to; 34 } 35 } 36 if(h[T]==-1)return 0; 37 return 1; 38 } 39 int dfs(int x,int f) 40 { 41 if(x==T)return f; 42 int w,used=0; 43 for(int i=cur[x];i;i=e[i].next) 44 if(h[e[i].to]==h[x]+1) 45 { 46 w=f-used;w=dfs(e[i].to,min(e[i].v,w)); 47 e[i].v-=w;if(e[i].v)cur[x]=i;e[i^1].v+=w; 48 used+=w;if(used==f)return f; 49 } 50 if(!used)h[x]=1; 51 return used; 52 } 53 void dinic() 54 {while(bfs()){for(int i=0;i<=T;i++)cur[i]=head[i];dfs(0,inf);}} 55 void build() 56 { 57 for(int i=1;i<=n;i++) 58 if(in[i]>0)insert(0,i,in[i]); 59 else insert(i,T,-in[i]); 60 } 61 bool jud() 62 { 63 for(int i=head[0];i;i=e[i].next) 64 if(e[i].v)return 0; 65 return 1; 66 } 67 int main() 68 { 69 int test=read(); 70 while(test--) 71 { 72 cnt=1; 73 memset(head,0,sizeof(head)); 74 memset(in,0,sizeof(in)); 75 n=read();m=read(); 76 for(int i=1;i<=m;i++) 77 { 78 int u,v,w; 79 u=read();v=read();low[i]=read();w=read(); 80 in[u]-=low[i];in[v]+=low[i]; 81 insert(u,v,w-low[i]); 82 } 83 build(); 84 dinic(); 85 if(!jud())printf("NO\n"); 86 else 87 { 88 printf("YES\n"); 89 for(int i=1;i<=m;i++) 90 printf("%d\n",e[(i<<1)^1].v+low[i]); 91 } 92 puts(""); 93 } 94 return 0; 95 }