有上下界的网络流

一、无源汇上下界网络可行流

无源汇上下界网络可行流  给定 $n$ 个点，$m$ 条边，每条边 $e$ 有一个流量下界 $l_e$ 和流量上界 $r_e$，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

这是一个判定。不同于一般的网络流，这个模型中没有源点与汇点，而且增加了每条边的流量限制 $[l_e,r_e]$，而一般的网络流只有最大流量限制，可以视为特殊的上下界网络流（$l_e=0$）。

首先考虑消除下界流量带来的影响。因为下界流量是必须流到的，不妨先强制流满下界流量。而这也带来了影响——这样操作之后每个点的初始含流量不再为 $0$，可以理解成，操作之后，每个节点多余若干流量或缺少若干流量，这是由于强制流满下界而未保证流量守恒导致的。

这样，记 $left_i$ 表示节点 $i$ 经过上述操作所剩余（用正表示） / 缺少（用负表示）的流量，并建立超级源点 $s$ 与超级汇点 $t$：

  • 若 $left_i>0$，即该节点流满下界时剩余 $left_i$ 单位流量，应多补给 $left_i$ 单位流量才能保证流满边的下界并流量守恒，所以需要从源点 $s$ 向 $i$ 连流量为 $left_i$ 的边；
  • 若 $left_i<0$，即该节点流满下界时缺少 $left_i$ 单位流量，应少供给 $left_i$ 单位流量才能保证流满边的下界并流量守恒，所以需要从 $i$ 向汇点 $t$ 连流量为 $-left_i$ 的边。

上面两个连边方式容易记混淆，务必深刻理解。

然后正常从超级源点 $s$ 到超级汇点 $t$ 跑网络流。网络有可行流当且仅当从超级源点流出的边均流满。

下面是算法流程：

  1. 强制流满每条边的下界 $l_e$，并根据流量记录每个点应剩余 / 缺少的流量值 $left_i$。
  2. 建立超级源点 $s$ 与超级汇点 $t$，按上述方式进行连边。
  3. 从 $s$ 到 $t$ 进行常规网络流算法。
  4. 检验网络流量是否与超级源点 $s$ 的出边流量和相等，相等则有可行流，否则没有。

模板题 LOJ #155. 无源汇有上下界可行流，参考代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 50005
#define inf 0x3f3f3f3f
int n,m,lft[MAXN],s,t,total,ans,idx[MAXN];
int head[MAXN],to[MAXN],nxt[MAXN],edge[MAXN],tot=1;
int now[MAXN],dep[MAXN];
struct node{
    int u,v,l,r;
}a[MAXN];
queue<int> q;
void add(int x,int y,int c){
    to[++tot]=y,edge[tot]=c,nxt[tot]=head[x],head[x]=tot;
    to[++tot]=x,edge[tot]=0,nxt[tot]=head[y],head[y]=tot;
}
bool bfs(){
    while(q.size()) q.pop();
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    q.push(s);
    now[s]=head[s];
    bool flag=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(edge[i]&&!dep[v]){
                dep[v]=dep[u]+1;
                now[v]=head[v];
                q.push(v);
                if(v==t) flag=1;
            }
            
        }
    }
    return flag;
}
int dinic(int u,int flow){
    if(u==t) return flow;
    int rest=flow;
    for(int i=now[u];i;i=nxt[i],now[u]=i){
        int v=to[i];
        if(edge[i]&&dep[v]==dep[u]+1){
            int k=dinic(v,min(edge[i],rest));
            if(!k) dep[v]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
            if(!rest) break;
        }
    }
    return flow-rest;
}
int main(){
    cin>>n>>m;
    s=n+1,t=n+2;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].l>>a[i].r;
        lft[a[i].u]-=a[i].l;
        lft[a[i].v]+=a[i].l;
        idx[i]=tot+1;
        add(a[i].u,a[i].v,a[i].r-a[i].l);
    }
    for(int i=1;i<=n;i++){
        if(lft[i]>0){
            add(s,i,lft[i]);
            total+=lft[i];
        }
        else add(i,t,-lft[i]);
    }
    int flow;
    while(bfs()){
        while(flow=dinic(s,inf)) ans+=flow;
    }
    if(ans==total){
        cout<<"YES"<<endl;
        for(int i=1;i<=m;i++) cout<<a[i].r-edge[idx[i]]<<endl;
    }
    else cout<<"NO"<<endl;
    return 0;
}

二、有源汇上下界网络可行流

有源汇上下界网络可行流  给定 $n$ 个点，$m$ 条边，每条边 $e$ 有一个流量下界 $l_e$ 和流量上界 $r_e$，给定源点 $s$ 和汇点 $t$，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

加入一条从汇点 $t$ 连向源点 $s$ 的流量上下界为 $[0,+\infty)$ 的边，转化成无源汇上下界网络可行流。之后新建超级源点 $S$ 与超级汇点 $T$，按上节方式连边进行网络最大流算法进行判定即可。

另外，我们还可以根据残量网图中 $t\rightarrow s$ 的边的剩余流量计算出网络可行流的大小。

三、有源汇上下界网络最大流

有源汇上下界网络最大流  给定 $n$ 个点，$m$ 条边，每条边 $e$ 有一个流量下界 $l_e$ 和流量上界 $r_e$，给定源点 $s$ 和汇点 $t$，求网络中的最大流，使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

先进行有源汇上下界网络可行流算法，之后得到残量网图与可行流大小。删除额外建立的 $t\rightarrow s$ 边，重新在残量网图上以 $s$ 为源点，$t$ 为汇点进行最大流算法。

则网络中的最大流为可行流与残量网图最大流之和。

模板题 LOJ #116. 有源汇有上下界最大流，参考代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 50005
#define inf 0x3f3f3f3f
int n,m,s,t,res[MAXN],ans;
int head[MAXN],nxt[MAXN],to[MAXN],edge[MAXN],tot=1;
int now[MAXN],d[MAXN];
queue<int> q;
struct node{
    int x,y,l,r;
}e[MAXN];
void add(int x,int y,int w){
    to[++tot]=y,edge[tot]=w,nxt[tot]=head[x],head[x]=tot;
    to[++tot]=x,edge[tot]=0,nxt[tot]=head[y],head[y]=tot;
}
bool bfs(){
    while(q.size()) q.pop();
    memset(d,0,sizeof(d));
    d[s]=1;
    now[s]=head[s];
    q.push(s);
    bool flag=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(edge[i]&&!d[v]){
                d[v]=d[u]+1;
                now[v]=head[v];
                q.push(v);
                if(v==t) flag=1;
            }
        }
    }
    return flag;
}
int dinic(int u,int flow){
    if(u==t) return flow;
    int rest=flow;
    for(int i=now[u];i;i=nxt[i],now[u]=i){
        int v=to[i];
        if(edge[i]&&d[v]==d[u]+1){
            int k=dinic(v,min(edge[i],rest));
            if(!k) d[v]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
            if(!rest) break;
        }
    }
    return flow-rest;
}
int main(){
    int s0,t0;
    cin>>n>>m>>s0>>t0;
    for(int i=1;i<=m;i++){
        cin>>e[i].x>>e[i].y>>e[i].l>>e[i].r;
        res[e[i].x]-=e[i].l;
        res[e[i].y]+=e[i].l;
        add(e[i].x,e[i].y,e[i].r-e[i].l);
    }
    s=n+1,t=n+2;
    int num=0;
    for(int i=1;i<=n;i++){
        if(res[i]>0){
            add(s,i,res[i]);
            num+=res[i];
        }
        else add(i,t,-res[i]);
    }
    add(t0,s0,inf);
    int flow,cnt=0;
    while(bfs()){
        while(flow=dinic(s,inf)) cnt+=flow;
    }
    if(cnt!=num){
        cout<<"please go home to sleep"<<endl;
        return 0;
    }
    s=s0,t=t0;
    ans=edge[tot];
    edge[tot]=edge[tot-1]=0;
    while(bfs()){
        while(flow=dinic(s,inf)) ans+=flow;
    }
    cout<<ans<<endl;
    return 0;
}

四、有源汇上下界网络最小流

有源汇上下界网络最小流  给定 $n$ 个点，$m$ 条边，每条边 $e$ 有一个流量下界 $l_e$ 和流量上界 $r_e$，给定源点 $s$ 和汇点 $t$，求网络中的最小流，使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

与一般网络流不同，因为每条边添加了下界限制，所以网络最小流不一定为 $0$，另需算法计算。

这个算法与上节大致类似，唯一不同在于：在残量网图中，进行源点为 $t$，汇点为 $s$ 的最大流算法。答案就是可行流大小减去上述计算的最大流大小。

这个操作实际上是通过反向网络的最大值尽可能大地消去网络可行流，求出最小流。

模板题 LOJ #117. 有源汇有上下界最小流，参考代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 500005
#define inf 0x3f3f3f3f
int n,m,s,t,res[MAXN],ans;
int head[MAXN],nxt[MAXN],to[MAXN],edge[MAXN],tot=1;
int now[MAXN],d[MAXN];
queue<int> q;
struct node{
    int x,y,l,r;
}e[MAXN];
void add(int x,int y,int w){
    to[++tot]=y,edge[tot]=w,nxt[tot]=head[x],head[x]=tot;
    to[++tot]=x,edge[tot]=0,nxt[tot]=head[y],head[y]=tot;
}
bool bfs(){
    while(q.size()) q.pop();
    memset(d,0,sizeof(d));
    d[s]=1;
    now[s]=head[s];
    q.push(s);
    bool flag=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(edge[i]&&!d[v]){
                d[v]=d[u]+1;
                now[v]=head[v];
                q.push(v);
                if(v==t) flag=1;
            }
        }
    }
    return flag;
}
int dinic(int u,int flow){
    if(u==t) return flow;
    int rest=flow;
    for(int i=now[u];i;i=nxt[i],now[u]=i){
        int v=to[i];
        if(edge[i]&&d[v]==d[u]+1){
            int k=dinic(v,min(edge[i],rest));
            if(!k) d[v]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
            if(!rest) break;
        }
    }
    return flow-rest;
}
int main(){
    int s0,t0;
    cin>>n>>m>>s0>>t0;
    for(int i=1;i<=m;i++){
        cin>>e[i].x>>e[i].y>>e[i].l>>e[i].r;
        res[e[i].x]-=e[i].l;
        res[e[i].y]+=e[i].l;
        add(e[i].x,e[i].y,e[i].r-e[i].l);
    }
    s=n+1,t=n+2;
    int num=0;
    for(int i=1;i<=n;i++){
        if(res[i]>0){
            add(s,i,res[i]);
            num+=res[i];
        }
        else add(i,t,-res[i]);
    }
    add(t0,s0,inf);
    int flow,cnt=0;
    while(bfs()){
        while(flow=dinic(s,inf)) cnt+=flow;
    }
    if(cnt!=num){
        cout<<"please go home to sleep"<<endl;
        return 0;
    }
    s=t0,t=s0;
    ans=edge[tot];
    edge[tot]=edge[tot-1]=0;
    while(bfs()){
        while(flow=dinic(s,inf)) ans-=flow;
    }
    cout<<ans<<endl;
    return 0;
}

五、无源汇上下界网络最小费用可行流

无源汇上下界网络最小费用可行流  给定 $n$ 个点，$m$ 条边，每条边 $e$ 有一个流量下界 $l_e$ 、流量上界 $r_e$，和单位流量花费 $c_e$，求一种花费最小的可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

与无源汇上下界网络可行流算法类似。唯一不同点在于将最大流算法替换为费用流算法。

需要注意的是，与超级源点与超级汇点连的边的费用为 $0$。