题解：P14579 【模板】有源汇上下界最大流

· · 题解

1.27 修复了一处图误。\ 1.27 修复了一处代码错误。

1. 无源汇上下界可行流

模板题

1.1 什么是上下界网络流

相比与一般的网络流，上下界网络流多了一个下界，即规定经过这条边的流量不能低于这个下界。

这时，我们容易想到按上界和下界之差建图，再跑一遍最大流，看看是否能流到 t。

但是，上下界网络流还要求我们每个点流量平衡，即每个点流入流量等于流出流量。如果按上界和下界之差建图，由于下界不同，很容易导致不满足平衡性。

1.2 解法

这里我们引入样例的图：

我们先以上界和下界之差建图，我们称之为增量网络。

再以每条边的下界建图，我们称之为下界网络。

容易发现，在下界网络中，有许多点入流与出流不对等。例如节点 1，入流为 1，出流为 3。为了使得平衡，我们在增量网络中新建源点 s 和汇点 t。

如果节点 i 出流之和比入流大，便连 i 向节点 t 的边，边权为出流之和与入流之和的差。如果入流之和比出流大，便连 s 向 i 的边，边权也为入流之和与出流之和的差。如果相等，则不连。

为什么要这么做呢？我们知道，如果仅在增量网络上跑可行流，不能保证平衡性。而我们上述做的事正是为了保证平衡。 \ （注意：是下界网络的出流入流之差，但连在增量网络上）

然后就可以在这张网络上愉快地跑最大流了。

那如何判断是否存在可行流呢？

其实就是判断新建的与 s 相连的边是否满流即可，如果都满流，就说明存在可行流。

每条边的实际流量就是增量网络上的流量加上下界。

1.3 代码

思路都在上文讲过，代码中就不多加赘述。 :::success[Code]

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
const int inf=1e18;
int n,m,s,t;
int u[maxn],v[maxn],l[maxn],r[maxn];
int e_id[maxn];
int f[maxn];
struct node{
    int to,next,w,type;
}e[2*maxn];
int head[maxn],tot=1;
void add(int u,int v,int w,int type){
    e[++tot].to=v;
    e[tot].w=w; e[tot].type=type;
    e[tot].next=head[u];
    head[u]=tot;
}
int dep[maxn],cur[maxn];
bool bfs(){
    queue<int> q;
    memset(dep,-1,sizeof(dep));
    q.push(s); dep[s]=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dep[v]==-1&&e[i].w){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=-1;
}
int dfs(int u,int flow){
    if(u==t) return flow;
    int used=flow;
    for(int i=cur[u];i;i=e[i].next){
        cur[u]=i;
        int v=e[i].to;
        if(dep[v]==dep[u]+1&&e[i].w){
            int rlow=dfs(v,min(used,e[i].w));
            e[i].w-=rlow; e[i^1].w+=rlow;
            used-=rlow;
            if(used==0) break;
        }
    }
    return flow-used;
}
void dinic(){
    int ans=0;
    while(bfs()){
        memcpy(cur,head,sizeof(head));
        ans+=dfs(s,inf);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m; s=0,t=n+1;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>l[i]>>r[i];
        f[u[i]]-=l[i]; f[v[i]]+=l[i];
        add(u[i],v[i],r[i]-l[i],0);
        e_id[i]=tot;
        add(v[i],u[i],0,1);
    }
    for(int i=1;i<=n;i++){
        if(f[i]<0) add(i,t,-f[i],2),add(t,i,0,1);
        else if(f[i]>0) add(s,i,f[i],2),add(i,s,0,1);
    }
    dinic();
    bool flag=1;
    for(int i=head[s];i;i=e[i].next){
        if(e[i].w&&e[i].type==2){
            flag=0; break;
        }
    }
    if(!flag){
        cout<<"No"; return 0;
    }
    cout<<"Yes\n";
    for(int i=1;i<=m;i++){
        int cap=r[i]-l[i];
        cout<<l[i]+cap-e[e_id[i]].w<<endl;
    }
    return 0;
}

:::

2. 有源汇上下界可行流

我们已经学会了无源汇上下界可行流，那如何解决有源汇上下界可行流问题呢？

2.1 解法

很简单对吧，只需要有源汇转无源汇即可。怎么转呢？我们可以建一条从 t 向 s 的边，边权赋为无穷大。这代表所有从 s 流向 t 的流量都会重新流向 s。这样，我们就完成了有源汇转无源汇。最后像无源汇上下界可行流那样做一遍即可。

依然拿上面的图演示：

2.2 代码

:::success[Code]

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
const int inf=1e18;
int n,m,S,T,sum;
int u[maxn],v[maxn],l[maxn],r[maxn];
int f[maxn];
struct node{
    int to,next,w;
}e[2*maxn];
int head[maxn],tot=1;
void add(int u,int v,int w){
    e[++tot].to=v;
    e[tot].w=w;
    e[tot].next=head[u];
    head[u]=tot;
}
int dep[maxn],cur[maxn];
bool bfs(int s,int t){
    queue<int> q;
    memset(dep,-1,sizeof(dep));
    q.push(s); dep[s]=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dep[v]==-1&&e[i].w){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=-1;
}
int dfs(int u,int flow,int t){
    if(u==t) return flow;
    int used=flow;
    for(int i=cur[u];i;i=e[i].next){
        cur[u]=i;
        int v=e[i].to;
        if(dep[v]==dep[u]+1&&e[i].w){
            int rlow=dfs(v,min(used,e[i].w),t);
            e[i].w-=rlow; e[i^1].w+=rlow;
            used-=rlow;
            if(used==0) break;
        }
    }
    return flow-used;
}
int dinic(int s,int t){
    int ans=0;
    while(bfs(s,t)){
        memcpy(cur,head,sizeof(head));
        ans+=dfs(s,inf,t);
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int s,t;
    cin>>n>>m>>s>>t; S=0,T=n+1;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>l[i]>>r[i];
        f[u[i]]-=l[i]; f[v[i]]+=l[i];
        add(u[i],v[i],r[i]-l[i]); add(v[i],u[i],0);
    }
    for(int i=1;i<=n;i++){
        if(f[i]<0) add(i,T,-f[i]),add(T,i,0);
        else if(f[i]>0) add(S,i,f[i]),add(i,S,0),sum+=f[i];
    }
    add(t,s,inf); add(s,t,0);
    return 0;
}

:::

3. 有源汇上下界最大流

模板题

3.1 解法

学会了有源汇上下界可行流，有源汇上下界最大流就很简单了。

but

并不是直接在增量网络上跑最大流，而是在跑完可行流后，再去跑最大流。

why

我的理解是，你要跑最大流，至少得保证存在可行流吧。所以呢，就得在跑完可行流的基础上去跑最大流。

也就是说，在跑完可行流后，我们要删除一开始建的超源超汇及相连的边，然后在残留网络上跑最大流。

最后的答案即为可行流的流量（即 t 到 s 边的实际流量）加跑出的增量最大流。

为了方便删边，我们将 t 到 s 放在最后连。

3.2 代码

:::success[Code]

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
const int inf=1e18;
int n,m,S,T,sum;
int u[maxn],v[maxn],l[maxn],r[maxn];
int f[maxn];
struct node{
    int to,next,w;
}e[2*maxn];
int head[maxn],tot=1;
void add(int u,int v,int w){
    e[++tot].to=v;
    e[tot].w=w;
    e[tot].next=head[u];
    head[u]=tot;
}
int dep[maxn],cur[maxn];
bool bfs(int s,int t){
    queue<int> q;
    memset(dep,-1,sizeof(dep));
    q.push(s); dep[s]=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dep[v]==-1&&e[i].w){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=-1;
}
int dfs(int u,int flow,int t){
    if(u==t) return flow;
    int used=flow;
    for(int i=cur[u];i;i=e[i].next){
        cur[u]=i;
        int v=e[i].to;
        if(dep[v]==dep[u]+1&&e[i].w){
            int rlow=dfs(v,min(used,e[i].w),t);
            e[i].w-=rlow; e[i^1].w+=rlow;
            used-=rlow;
            if(used==0) break;
        }
    }
    return flow-used;
}
int dinic(int s,int t){
    int ans=0;
    while(bfs(s,t)){
        memcpy(cur,head,sizeof(head));
        ans+=dfs(s,inf,t);
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int s,t;
    cin>>n>>m>>s>>t; S=0,T=n+1;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>l[i]>>r[i];
        f[u[i]]-=l[i]; f[v[i]]+=l[i];
        add(u[i],v[i],r[i]-l[i]); add(v[i],u[i],0);
    }
    for(int i=1;i<=n;i++){
        if(f[i]<0) add(i,T,-f[i]),add(T,i,0);
        else if(f[i]>0) add(S,i,f[i]),add(i,S,0),sum+=f[i];
    }
    add(t,s,inf); add(s,t,0);//连t到s
    if(dinic(S,T)!=sum){
        cout<<"N";
        return 0;
    }//没有可行流
    int ans1=inf-e[tot^1].w;//t到s边的实际流量
    e[tot].w=e[tot^1].w=0;//删边
    cout<<ans1+dinic(s,t);//答案=t到s边的实际流量+增量最大流
    return 0;
}

:::