更好的阅读体验：My blog

浅谈上下界网络流

参考资料：liu_runda’s blog,red’s blog

PS:左侧可以跳转

无源汇有上下界可行流(循环流)

给一个网络，求一个流满足：每条边$i$流量在$[low(i),upp(i)]$之间，每个点$u$都要满足流量守恒(即$\sum_{to_i=u}f(i)=\sum_{from_i=u}f(i)$)

[HTML_REMOVED]

可行流算法的核心是将一个不满足流量守恒的初始流调整成满足流量守恒的流. -liu_runda

初始流即一开始将每条边流量设为$low(i)$的流。显然这个流不一定满足流量守恒。我们要通过调整（再加上一个附加流）将其变为可行流

记$a(u)=\sum_{to_i=u}f(i)-\sum_{from_i=u}f(i)$,即初始流中，点$u$的流入量-流出量。

在附加流中，让点$u$的流入量-流出量=$-a(u)$,就能保证流量守恒。

• 当$-a(u)<0\ (a(u)>0)$,需要让$u$的流入量增加$a(u)$.这可以通过新建超级源点$S$,并增加$S\rightarrow u,$容量为$a(u)$的边做到。
• 当$-a(u)>0\ (a(u)<0)$需要让$u$的流出量增加$a(u)$.这可以通过新建超级汇点$T$,并增加$u\rightarrow T,$容量为$-a(u)$的边做到。

另外，对于原图中的边$i$,还有$upp(i)-low(i)$的容量，也要加上。

与$S,T$相邻的边都满流 加上附加流后每个点都满足流量守恒

因此，跑一下$S$到$T$的最大流，若与$S,T$相邻的边都满流，则存在可行流。每条边的具体流量即为$low(i)+i$在附加流中的流量（即反边容量）。

ll Dinic(ll s,ll t,ll n){....}
//略去了Dinic板子
ll a[MAXN],low[MAXM],upp[MAXM];
int main()
{
    ll n=read(),m=read(),S=n+1,T=S+1;
    for(ll i=1;i<=m;++i)
    {
        ll u=read(),v=read();low[i]=read(),upp[i]=read();
        a[u]-=low[i],a[v]+=low[i];adde(u,v,upp[i]-low[i]);
    }
    ll sum=0;
    for(ll i=1;i<=n;++i)
        if(a[i]>0)sum+=a[i],adde(S,i,a[i]);
        else if(a[i]<0)adde(i,T,-a[i]);
    ll f=Dinic(S,T,T);
    if(f<sum)return puts("NO")&0;
    puts("YES");
    for(ll i=1;i<=m;++i)printf("%lld\n",e[i<<1|1].w+low[i]);//e[i<<1|1].w表示反边容量，即附加流中的流量
    return 0;
}

有源汇有上下界最大流

在有源汇的网络流图中，源点$rS$、汇点$rT$不满足流量守恒，无法直接跑循环流。

但只要加一条$rT\rightarrow rS$,下界为0上界为正无穷的边，就能保证流量守恒。跑一下超源$S$到$T$的最大流，得到可行流，可行流中$rT\rightarrow rS$的流量即为$rS\rightarrow rT$的真正流量，记为$f1$.

删掉$rT\rightarrow rS$的边，再跑一次$rS\rightarrow rT$的最大流$f2$,答案即为$f1+f2$

My code

有源汇有上下界最小流

基本与前者类似，用$f1$减掉$rT$流向$rS$的最大流$f3$(即回退这些流)即为答案。
My code