题解

先考虑无源汇的情况。将每条边的权值都设为$l_i$，但是此时图中不满足每个点流出和流入相等的限制，所以对于每个点，如果它的流入大于流出，由超级源点$S$向其连一条流入-流出的边，表示流出还应增加多少；如果它的流出大于流入，由其向超级汇点$T$连一条流出-流入的边，表示流入还应增加多少，对于原来的每条边建成权值为$r_i-l_i$的边，表示最多可以让起点的流出，终点的流入增加多少。然后再跑最大流。如果每个点在调整后都能满足流入=流出的限制(显然$S$连出去的边的总权值等于连向$T$的边的总权值，所以限制等价于这些边都能流满)，则存在可行流。
如果原图中有源汇，则为了让每个点仍保持流入等于流出的限制，可以先建一条由汇点到源点的上下界分别为$0$和$inf$的边，转换成无源汇的问题。(此时源点到汇点的最大流就等于这条边的流量)

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const int inf = 0x7fffffff; 

int Case;
int n,m,S,T,cnt;
int head[N],d[N];
int fin[N],fout[N],ide[N];
struct nd{
	int ne,to,w;
}e[N<<1];
struct Edge{
	int x,y,l,r;
}a[N];

void in(int x,int y,int w){
	e[++cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;e[cnt].w=w;
	e[++cnt].to=x;e[cnt].ne=head[y];head[y]=cnt;e[cnt].w=0;
}

bool bfs(){
	static queue<int>q;
	for(int i=1;i<=T;++i)d[i]=0;
	q.push(S);d[S]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=e[i].ne){
			int y=e[i].to;
			if(!d[y]&&e[i].w>0){
				d[y]=d[x]+1;
				q.push(y);
			}
		}
	}
	return d[T]!=0;
}

int dinic(int x=S,int mn=inf){
	if(x==T||!mn)return mn;
	int flow=0;
	for(int i=head[x];i;i=e[i].ne){
		int y=e[i].to,maxf;
		if(d[y]==d[x]+1&&(maxf=dinic(y,min(mn,e[i].w)))>0){
			e[i].w-=maxf;e[i^1].w+=maxf;
			mn-=maxf;flow+=maxf;
			if(!mn)break;
		}
	}
	if(!flow)d[x]=0;
	return flow;
}

int main(){
	scanf("%d",&Case);
	while(Case--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n+2;++i)head[i]=fin[i]=fout[i]=0;
		cnt=1;
		for(int i=1;i<=m;++i){
			scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].l,&a[i].r);
			in(a[i].x,a[i].y,a[i].r-a[i].l);
			fin[a[i].y]+=a[i].l;
			fout[a[i].x]+=a[i].l;
			ide[i]=cnt;
		}
		S=n+1;T=n+2;
		int Maxflow=0;
		for(int i=1;i<=n;++i)
		if(fin[i]>=fout[i]){
			in(S,i,fin[i]-fout[i]);
			Maxflow+=fin[i]-fout[i];
		}
		else in(i,T,fout[i]-fin[i]);
		//in(t,s,inf); 
		while(bfs())Maxflow-=dinic();
		if(Maxflow!=0)puts("NO");
		else{
			puts("YES");
			for(int i=1;i<=m;++i)printf("%d\n",a[i].l+e[ide[i]].w);
		}
	}
}

上下界可行流

题解

代码