无源汇有上下界可行流

模板题

记第$i$条边的下界为$down_i$，上界为$up_i$。

我们先让每条边流下界的流量，即将每条边$i$的容量设为$up_i-down_i$，下界为$0$，现在我们能满足下界的要求了，但是流量是不守恒的。

建虚拟源点$S$和汇点$T$。

我们记每个点$x$的入流量为$in_x$，出流量为$out_x$，之后我们根据$in_x$和$out_x$的大小分类讨论：
1.(in_xgeqslant out_x)，这就意味$x$点要多向外输出$in_x-out_x$的流量，我们从$S$向$x$连$in_x-out_x$容量的边。
2.(in_xleqslant out_x)，这就意味$x$点要多从外输入$out_x-in_x$的流量，我们从$x$向$T$连$out_x-in_x$容量的边。

现在说为什么这么连边：
我们说明$S$向$x$连边的情况，另一种同理。
$x$现在需要流出$in_x-out_x$的流量才能守恒，我们从$S$给了$x$这么多流量，如果这股流满流，那么$x$就会满足要求，因为出流量必定增大了$in_x-out_x$。

之后我们求最大流，如果$S$流出的边有不满流的，就无解。

对于边$i$，它的真实流量就是下界+这条边流过的流量（即反边流量）。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=210;
const int maxm=10210;
const int inf=1e9;
int n,m,cnt_edge=1,sum,S,T;
int head[maxn],cur[maxn],in[maxn],out[maxn],dep[maxn];
struct Edge{int u,v,down,up;}E[maxm];
struct edge{int to,nxt,flow;}e[(maxn+maxm)<<1];
inline void add(int u,int v,int w)
{
	e[++cnt_edge].nxt=head[u];
	head[u]=cnt_edge;
	e[cnt_edge].to=v;
	e[cnt_edge].flow=w;
}
inline void addflow(int u,int v,int w){add(u,v,w);add(v,u,0);}
inline bool bfs()
{
    memset(dep,0,sizeof(dep));
    for(int i=S;i<=T;i++)cur[i]=head[i];
    queue<int>q;
    q.push(S);dep[S]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dep[y]||e[i].flow<=0)continue;
            dep[y]=dep[x]+1;q.push(y);
        }
    }
    return dep[T]>0;
}
int dfs(int x,int lim)
{
    if(x==T||lim<=0)return lim;
    int res=lim;
    for(int i=cur[x];i;i=e[i].nxt)
    {
        cur[x]=i;
        int y=e[i].to;
        if(dep[y]!=dep[x]+1||e[i].flow<=0)continue;
        int tmp=dfs(y,min(res,e[i].flow));
        if(tmp<=0)dep[y]=0;
        res-=tmp;
        e[i].flow-=tmp,e[i^1].flow+=tmp;
        if(res<=0)break;
    }
    return lim-res;
}
inline int Dinic()
{
	int res=0;
	while(bfs())res+=dfs(S,inf);
	return res;
}
int main()
{
	scanf("%d%d",&n,&m);
	S=0,T=n+1;
	for(int i=1;i<=m;i++)scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].down,&E[i].up);
	for(int i=1;i<=m;i++)in[E[i].v]+=E[i].down,out[E[i].u]+=E[i].down;
	for(int i=1;i<=m;i++)addflow(E[i].u,E[i].v,E[i].up-E[i].down);
	for(int i=1;i<=n;i++)
	{
		if(in[i]>=out[i])addflow(S,i,in[i]-out[i]),sum+=in[i]-out[i];
		else addflow(i,T,out[i]-in[i]);
	}
	if(Dinic()!=sum){puts("NO");return 0;}
	puts("YES");
	for(int i=2;i<=2*m+1;i+=2)printf("%d
",E[i/2].down+e[i^1].flow);
	return 0;
}