模型：一个网络，求出一个流，使得每条边的流量必须 \(\geq L_i\) 且 \(\leq Hi\),
每个点必须满足 总流入量 = 总流出量 (流量守恒)(这个流的特点是循环往复,无始无终)
可行流算法的核心是将一个不满足流量守恒的初始流调整成满足流量守恒的流
如果存在一个可行流,那么一定满足每条边的流量都大于等于流量的下限。
因此我们可以令每条边的流量等于流量下限，得到一个初始流，然后建出这个流的残量网络。
(即:每条边的流量等于这条边的流量上限与流量下限之差)
这个初始流不一定满足流量守恒，但是最终的可行流一定是在这个初始流的基础上增大了一些边的流量使得所有点满足流量守恒。
因此我们考虑在残量网络上求出一个另不满足流量守恒的附加流,
使得这个附加流和我们的初始流合并之后满足流量守恒
那么首先我们需要开一个数组 \(in[i]\) 表示 \(i\) 在初始流中的 流入量 - 流出量 的值。
那么 \(in[i]\) 的正负表示流入量和流出量的大小关系：
- \(in[i]>0\) ，说明附加流的流入量要小于流出量
- \(in[i]<0\) ，说明附加流的流入量要大于流出量
所以 \(in[i]=\) 附加流流出量 - 附加流流入量 。
下面就用 \(in[i]\) 表示初始流中i的流入量-流出量。
但是 \(dinic\) 算法能够求的是满足流量守恒的有源汇最大流，不能在原网络上直接求一个这样的无源汇且不满足流量守恒的附加流，注意到附加流是在原网络上不满足流量守恒的，这启发我们添加一些原网络之外的边和点，用这些边和点实现“原网络上流量不守恒”的限制。
具体地，如果一个点 \(i\) 在原网络上的附加流中需要满足 流入量 > 流出量 \((in[i]<0)\) ，那么我们需要给多的流入量找一个去处，因此我们建一条从 \(i\) 出发流量 \(=|in[i]|\)的边
如果 \(in[i]>0\) ，也就是我们需要让附加流中的 流出量>流入量 ，我们需要让多的流出量有一个来路，因此我们建一条指向 \(i\) 的流量 \(=|in[i]|\) 的边。
当然，我们所新建的从 \(i\) 出发的边也要有个去处，指向 \(i\) 的边也要有个来路，因此我们新建一个虚拟源点 \(S\) 和一个虚拟汇点 \(T\) ，新建的指向 \(i\) 的边都从 \(S\) 出发,从 \(i\) 出发的边都指向 \(T\)。
一个点要么有一条边指向 \(T\) ,要么有一条边来自\(S\) ，指向 \(T\) 的边的总流量上限一定等于 \(S\) 流出的边的总流量上限。
因为每一条边对两个点的 \(A[i]\) 贡献一正一负大小相等，所以全部点的 \(A[i]\) 之和等于 \(0\),
即小于 \(0\) 的 \(A[i]\) 之和的绝对值 = 大于 \(0\) 的 \(A[i]\) 之和的绝对值。
如果我们能找到一个流满足新加的边都满流,这个流在原图上的部分就是我们需要的附加流
那么怎样找出一个新加的边都满流的流呢？
可以发现假如存在这样的方案，这样的流一定是我们所建出的图的 \(S-T\) 最大流，
所以跑 \(S\) 到 \(T\) 的最大流即可。
如果最大流的大小等于 \(S\) 出发的所有边的流量上限之和，则存在这样的附加流满足题意
最后，每条边在 可行流中的流量 = 容量下界 + 附加流的流量 （即跑完 \(dinic\) 之后所加反向边的权值）
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define R register int
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
} const int N=210,M=21010,Inf=0x3f3f3f3f;
int n,m,cnt=1,s,t;
int vr[M],nxt[M],fir[N],w[M],in[N],b[M],d[N],cur[N];
inline void add(int u,int v,int ww) {
vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,w[cnt]=ww;
vr[++cnt]=u,nxt[cnt]=fir[v],fir[v]=cnt,w[cnt]=0;
}
queue<int> q;
inline bool bfs() {
memset(d,0,sizeof d),memcpy(cur,fir,sizeof fir);
q.push(s),d[s]=1; while(q.size()) { R u=q.front(); q.pop();
for(R i=fir[u];i;i=nxt[i]) if(w[i]) { R v=vr[i];
if(!d[v]) d[v]=d[u]+1,q.push(v);
}
} return d[t]>0;
}
inline int dfs(int u,int f) {
if(u==t||f<=0) return f; R res=f;
for(R& i=cur[u];i;i=nxt[i]) if(w[i]) {
R v=vr[i]; if(d[v]==d[u]+1) {
R tmp=dfs(v,min(res,w[i]));
if(!tmp) d[v]=0;
res-=tmp,w[i]-=tmp,w[i^1]+=tmp;
if(!res) return f;
}
} return f-res;
}
inline void main() {
n=g(),m=g();
for(R i=1,u,v,up,dn,w;i<=m;++i) {
u=g(),v=g(),dn=g(),up=g();
b[i]=dn,w=up-dn;
add(u,v,w),in[u]-=dn,in[v]+=dn;
} s=n+1,t=n+2; R sum=0,ans=0;
for(R i=1;i<=n;++i)
if(in[i]<0) add(i,t,-in[i]);
else add(s,i,in[i]),sum+=in[i];
while(bfs()) ans+=dfs(s,Inf);
puts(ans==sum?"YES":"NO");
if(ans==sum) for(R i=1;i<=m;++i)
printf("%d\n",w[i<<1|1]+b[i]);
}
} signed main() {Luitaryi::main(); return 0;}2019.12.26