P14578 【模板】无源汇上下界可行流 题解

前置知识

1. 最大流算法 (EK,Dinic 等)。

2. 网络流基本概念。

题目传送门

算法介绍

先说具体流程：

1. 读入时把 \(r_i-l_i\) 作为第 \(i\) 条边 \((u_i,v_i)\) 的边权。同时求出每个点 \(p\) 的 \(\sum\limits_{(u_i,p)\in E}l_i-\sum\limits_{(p,v_i)\in E}l_i\)，记作 \(w_p\)。

2. 若 \(w_i>0\) 从 \(S\) 向 \(i\) 连一条容量为 \(w_i\) 的边；若 \(w_i<0\) 从 \(i\) 向 \(T\) 连一条容量为 \(|w_i|\) 的边。

3. 跑最大流，记流量为 \(flow\)，若 \(flow=\sum\limits_{(S,v_i)\in E'}c_i\)，则存在可行流。

4. 输出方案：每条原边加下界即可。

正确性证明

以下内容为本人学习过程中结合多处资料，仔细思考后所总结的一种容易理解的解释方法，将详细解释每一步的缘由，同时排除一些误区，以及其他题解可能疏漏的细节。

初步理解：因为每条边有上下界流量限制，这类问题可能连可行流都不存在，所以上下界网络流先从无源汇上下界可行流入手。对于无源汇，可行流应该是在环上流的。

解析：

先在网络中把所有边的下界补充好，则初始的网络不一定是可行流 (不一定满足流量守恒)，考虑用每条边剩下的容量来使所有点达到流量守恒。

新建一张网络，边权改为原来的上下界之差，则要在这一张网络上求一个流，使其与初始网络的叠加是可行流。我们发现，这样的流仍然不应该满足流量守恒 (如果初始不满足)，进一步分析：

如果初始网络中：

1. 点 \(u\) 的流入流量 > 流出流量，把差值的绝对值记作 \(\Delta\)，则新网络中的该点应该是流出流量比流入流量多 \(\Delta\)，我们要强制点 \(u\) 的流出流量比流入流量多 \(\Delta\)，则建立超级源点，用源点向点 \(u\) 连 \(\Delta\) 容量的边，由于加了源点后我们再次使其满足了流量守恒，若忽略新加的边，该点的流出流量正好比流入流量多 \(\Delta\)。忽略新边的这一步其实是把两个图做了映射，完全等价。

2. 点 \(u\) 的流入流量 < 流出流量，把差值的绝对值记作 \(\Delta\)，从 \(u\) 向超级汇点连容量为 \(\Delta\) 的边。

由于我们是强制流量出现变化，且是通过超级源汇引入 / 导出流量实现的，所以为了满足强制条件，需要新加的边满流，即求出最大流，在判断是否满流即可。

---

细心的童鞋可能会想，判满流时，是判源点满流还是汇点满流呢？如果出现一个满一个不满怎么办？

其实这种情况是不存在的，即 \(\sum c(S,u)=\sum c(u,T)\)。由于每一条边的存在会使起点和终点的 \(\Delta\) 增减相同的值，所以 \(\sum \Delta=0\)，换个角度就是正权点之和的绝对值等于负权点之和的绝对值。那么，如果源点满流了，则汇点也一定满流了。

代码部分和最大流几乎一样。

:::info[Code]

#include <bits/stdc++.h>
using namespace std;

inline int read(){
    int d=0,f=0;char ch=getchar();
    while (!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while (isdigit(ch)) d=d*10+ch-'0',ch=getchar();
    return f?-d:d;
}

void write(int n) {if (n>9) write(n/10);putchar(n%10+'0');}

const int N=1005,M=10005,inf=2e9+7;

int n,m,h[N],idx,S,T,w[N],l[M],r[M];

struct Edge{int t,c,ne;}e[M<<1];
inline void add(int a,int b,int c){
    e[idx]={b,c,h[a]};h[a]=idx++;
    e[idx]={a,0,h[b]};h[b]=idx++;
}

int q[N],hh,tt,cur[N],d[N];

inline bool bfs(){
    memset(d,0,sizeof(int)*(T+1));
    hh=0,tt=-1,q[++tt]=S,d[S]=1;
    while (hh<=tt){
        int u=q[hh++];
        for (int i=h[u];~i;i=e[i].ne){
            int v=e[i].t;
            if (!d[v]&&e[i].c){
                d[v]=d[u]+1,q[++tt]=v;
                if (v==T) return true;
            }
        }
    }
    return false;
}

int dfs(int u,int mf){
    if (u==T) return mf;
    int sum=0;
    for (int &i=cur[u];~i;i=e[i].ne){
        int v=e[i].t;
        if (d[v]==d[u]+1&&e[i].c){
            int f=dfs(v,min(mf,e[i].c));
            sum+=f,mf-=f;
            e[i].c-=f,e[i^1].c+=f;
            if (!mf) break;
        }
    }
    if (!sum) d[u]=0;
    return sum;
}

inline int Dinic(){
    int flow=0;
    while (bfs()){
        memcpy(cur,h,sizeof(int)*(T+1));
        flow+=dfs(S,inf);
    }
    return flow;
}

int main(){
    n=read(),m=read(),S=0,T=n+1;
    
    memset(h,-1,sizeof(int)*(T+1));
    
    int sum=0;
    for (int i=1;i<=m;i++){
        int u=read(),v=read();
        l[i]=read(),r[i]=read();
        add(u,v,r[i]-l[i]);
        w[v]+=l[i],w[u]-=l[i];//出边减，入边加
    }
    for (int i=1;i<=n;i++)
        if (w[i]>0) add(S,i,w[i]),sum+=w[i];//采用判源点满流
        else add(i,T,-w[i]);

    int res=Dinic();
    if (res==sum) {//判可行流
        puts("Yes");
        for (int i=1;i<=m;i++) write(e[i*2-1].c+l[i]),putchar('\n');//加上下界
    }
    else puts("No");
    return 0;
}

:::

若有正确性证明不足，或不好理解的地方，望指出。