题意:有向图中有n(1 <= n <= 200)个点，无自环或者环的节点个数至少为3.给定每条边的最小流量和最大流量，问每条边的可行流量为多少?
思路:一般求解的网络流并不考虑下界问题，即流量可以为0，在有下界时，我们只需将上界变成r-l,这时还需要满足流量守恒，增加源点s和汇点t,当点u的流入大于流出时，将点u与s连边，容量即为多出的流量。同理当u流出大于流入时，多出来的流出的流量连到汇点t;直接跑最大流；这时得到的只是网络中的可行流；
为什么处理完下界之后是这样与超级源点和汇点连边的?
因为我们建的图是建立在每条边已经满足下界的情况下的，但是这时并没有实现流量的平衡。这时就需要显式地对没有流出的流量增加流入边，即上面当输入的流量-流出的流量>0时，与源点连边。因为我们之后跑完Dinic之后，看附加边是否满流，看的就是是否填补了下界没有流出去的流量。从而实现流量平衡；
ps:对于网络流问题，无论题目的是有向还是无向图，因为是增广搜索，所以一定是建无向图。。只是cap不同
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
#define lowbit(x) (x&(-x))
typedef pair<int,int> PII;
#define A first
#define B second
#define MK make_pair
typedef long long ll;
typedef unsigned int uint;
int i,j,k,n,m;
const int M = ;
int head[M],tot;
struct Edge{
int from,to,cap,flow,Next,id;
Edge(){}
Edge(int f,int to,int cap,int Next,int id):from(f),to(to),cap(cap),Next(Next),id(id),flow(){}
}e[M<<];
inline void ins(int u,int v,int w,int id)
{
e[++tot] = Edge{u,v,w,head[u],id};
head[u] = tot;
}
int s,t,cur[M],d[];
int que[];
bool BFS()
{
rep1(i,s,t) d[i] = -;
int l = ,r = ;
que[r++] = s;d[s] = ;
while(l < r){ //[l,r)
int u = que[l++];
for(int i = head[u];i;i = e[i].Next){
int v = e[i].to;
if(d[v] < && e[i].cap > e[i].flow){ // 只考虑残量网络的弧
d[v] = d[u] + ;//扑出路径来;
que[r++] = v;
if(v == t) return true;
}
}
}
return false;
}
int DFS(int x,int a)// a表示目前为止所有弧的最小残量
{
if(x == t || a == ) return a;
int& i = cur[x];//回溯时会多次DFS到同一个点
if(i == ) i = head[x];
int flow = , f;
for(;i;i = e[i].Next){// 从上次考虑的弧开始
int v = e[i].to;
if(d[v] == d[x]+ && (f = DFS(v,min(a,e[i].cap - e[i].flow))) > ){
e[i].flow += f;
e[i^].flow -= f;
flow += f;
a -= f;// 残量-流量
if(a == ) break;
}
}
return flow;
}
int Dinic()
{
int flow = ;
while(BFS()){//仍然存在增广路时再DFS
rep1(i,s,t) cur[i] = ;//记录当前探索到的点的弧的编号
flow += DFS(s,inf);
}
return flow;
}
int l[M],ans[M];
int main()
{
//freopen("data.txt","r",stdin);
//freopen("out.txt","w",stdout);
int kase = ;
while(scanf("%d%d",&n,&m) == ){
if(kase++) puts("");
MS0(head);tot = ;MS0(d);
int u,v,r;
s = ,t = n+;
rep1(i,,m){
scanf("%d%d%d%d",&u,&v,&l[i],&r);
d[u] -= l[i];
d[v] += l[i];
ins(u,v,r-l[i],i);
ins(v,u,,);
}
rep1(i,,n){
if(d[i] > ) ins(s,i,d[i],),ins(i,s,,);
if(d[i] < ) ins(i,t,-d[i],),ins(t,i,,);
}
Dinic();
bool flag = false;
for(int d = head[s];d;d = e[d].Next){
if(e[d].cap - e[d].flow){flag = true;break;}
}
if(flag){puts("NO");continue;}
puts("YES");
rep1(i,,tot)if(e[i].id){
ans[e[i].id] = e[i].flow+l[e[i].id];
}
rep1(i,,m) printf("%d\n",ans[i]);
}
return ;
}