秘制神奇上下界网络流%%%html
什么什么有（木）源汇可行流什么的，，看不懂（一下纯属我的sb言论）c++
看了半天知道点，一个点u，从S连到u的流量是所有流入u的下界，u到T是所有流出u的下界和。（进去出来的约一下）网络
感受这个的意思就是保持从进入到出来的下界都符合（强行构造相等？？），而且若是能满流，则上界也符合。那么就是可行的。post
看了个有上下界最大流什么的，连一个从T-S的边，而后原图就成了无原汇了，那么再加TT，SS，搞上面的，判断可行的同时能够得出来S-T的流量，是一个可行流量。设为sum1.ui
那么去掉S-T的边和SS，TT点，在跑了一遍的图上跑最大流，就是使原有的图继续增广，能够得出另外一个最大流sum2，那么ans=sum1+sum2。（就看了这么一点，sb）spa
1 #include<bits/stdc++.h> 2 #define N 100005 3 #define LL long long 4 #define inf 0x3f3f3f3f 5 #define ls tr[x][0] 6 #define rs tr[x][1] 7 using namespace std; 8 inline int ra() 9 { 10 int x=0,f=1; char ch=getchar(); 11 while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} 12 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 13 return x*f; 14 } 15 const int S=0,T=201; 16 int n,m,cnt; 17 int head[205],cur[205],h[205],q[2050],in[205]; 18 int low[100005]; 19 struct data{int to,next,v;}e[100005]; 20 void ine(int x, int y, int v) 21 { 22 e[++cnt].to=y; 23 e[cnt].next=head[x]; 24 e[cnt].v=v; 25 head[x]=cnt; 26 } 27 void insert(int x, int y, int v) 28 { 29 ine(x,y,v); ine(y,x,0); 30 } 31 bool bfs() 32 { 33 for (int i=1; i<=T; i++) h[i]=-1; 34 int l=0,r=1; q[0]=S; h[S]=0; 35 while (l<r) 36 { 37 int x=q[l++]; 38 for (int i=head[x];i;i=e[i].next) 39 if (e[i].v && h[e[i].to]==-1) 40 { 41 h[e[i].to]=h[x]+1; 42 q[r++]=e[i].to; 43 } 44 } 45 if (h[T]==-1) return 0; 46 return 1; 47 } 48 int dfs(int x, int f) 49 { 50 if (x==T) return f; 51 int w,ww=0; 52 for (int i=head[x];i;i=e[i].next) 53 if (h[e[i].to]==h[x]+1) 54 { 55 w=dfs(e[i].to,min(e[i].v,f-ww)); 56 ww+=w; e[i].v-=w; e[i^1].v+=w; 57 if (ww==f) return f; 58 } 59 if (!ww) h[x]=-1; 60 return ww; 61 } 62 void dinic() 63 { 64 while (bfs()) dfs(S,inf); 65 } 66 void build() 67 { 68 for (int i=1; i<=n; i++) 69 if (in[i]>0) insert(S,i,in[i]); 70 else insert(i,T,-in[i]); 71 } 72 bool jud() 73 { 74 for (int i=head[S];i;i=e[i].next) 75 if (e[i].v) return 0; 76 return 1; 77 } 78 int main() 79 { 80 int t=ra(); 81 while (t--) 82 { 83 cnt=1; 84 memset(head,0,sizeof(head)); 85 memset(in,0,sizeof(in)); 86 n=ra(); m=ra(); 87 for (int i=1; i<=m; i++) 88 { 89 int x=ra(),y=ra(); low[i]=ra(); int w=ra(); 90 in[x]-=low[i]; in[y]+=low[i]; 91 insert(x,y,w-low[i]); 92 } 93 build(); dinic(); 94 if (!jud()) cout<<"NO"<<endl; 95 else{ 96 cout<<"YES"<<endl; 97 for (int i=1; i<=m; i++) 98 printf("%d\n",e[(i<<1)^1].v+low[i]); 99 } 100 cout<<endl; 101 } 102 return 0; 103 }