@H_
404_0@
@H_
404_0@
每条边的容量满足一定的限制，即有一个上限值，也有一个下限值
@H_
404_0@
上界用ci表示，下界用bi表示。
@H_
404_0@
下界是必须流满的，那么对于每一条边，去掉下界后，其自由流为ci– bi。
@H_
404_0@
主要思想：每一个点流进来的流=流出去的流
@H_
404_0@
对于每一个点i，令
@H_
404_0@
Mi= sum(i点所有流进来的下界流)– sum(i点所有流出去的下界流)
@H_
404_0@
如果Mi大于0，代表此点必须还要流出去Mi的自由流，那么我们从源点连一条Mi的边到该点。
@H_
404_0@
如果Mi小于0，代表此点必须还要流进来Mi的自由流，那么我们从该点连一条Mi的边到汇点。
@H_
404_0@
如果求S->T的最大流，看是否满流(S的相邻边都流满)。
@H_
404_0@
满流则有解，否则无解。
@H_
404_0@
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 410
#define maxm 40003
#define inf 1000000000
int min(int a,int b)
{
return a < b ? a : b;
}
struct E
{
int v,next,c;
}edge[maxm];
int head[maxn],tot;
int n,m;
int S,T;
void add(int s,int t,int c)
{
edge[tot].v = t;
edge[tot].c = c;
edge[tot].next = head[s];
head[s] = tot++;
edge[tot].v = s;
edge[tot].c = 0;
edge[tot].next = head[t];
head[t] = tot++;
}
void init()
{
tot = 0;
memset(head,-1,sizeof(head));
}
int gap[maxn],dis[maxn],pre[maxn],cur[maxn];
int sap(int s,int vs)// s 源点，t汇点，vs顶点总数
{
int i;
for(i = 0; i <= vs; i++)
{
dis[i] = gap[i] = 0;
cur[i] = head[i];
}
gap[0] = vs;
int u = pre[s] = s,maxf = 0,aug = inf,v;
while(dis[s] < vs)
{
loop: for(i = cur[u]; i != -1; i = edge[i].next)
{
v = edge[i].v;
if(edge[i].c > 0 && dis[u] == dis[v] + 1)
{
aug = min(aug,edge[i].c);
pre[v] = u;
cur[u] = i;
u = v;
if(u == t)
{
while(u != s)
{
u = pre[u];
edge[cur[u]].c -= aug;
edge[cur[u]^1].c += aug;
}
maxf += aug;
aug = inf;
}
goto loop;
}
}
int min_d = vs;
for(i = head[u]; i != -1; i = edge[i].next)
{
v = edge[i].v;
if(edge[i].c > 0 && dis[v] < min_d)
{
min_d = dis[v];
cur[u] = i;
}
}
if( !(--gap[dis[u]])) break;
++gap[dis[u] = min_d + 1];
u = pre[u];
}
return maxf;
}
int in[maxn];
int low[maxm];
int main()
{
int i,j,cas;
int a,b,c;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&n,&m);
init();
memset(in,sizeof(in));
for(i = 0; i < m; i++)
{
scanf("%d%d%d%d",&a,&b,&low[i],&c);
in[b] += low[i]; in[a] -= low[i];
add(a,c - low[i]);
}
S = 0,T = n+1;
for(i = 1; i <= n; i++)
{
if(in[i] > 0) add(S,i,in[i]);
if(in[i] < 0) add(i,T,-in[i]);
}
sap(S,n+2);
bool flag = 1;
for(i = head[S]; i != -1; i = edge[i].next)
{
if(edge[i].c > 0) { flag = 0; break;}
}
if(flag)
{
printf("YES\n");
for(i = 0; i < m; i++)
printf("%d\n",edge[(i<<1)^1].c + low[i]);
}
else printf("NO\n");
if(cas) puts("");
}
return 0;
}
