有上下界的网络流/费用流 学习笔记 [网络流]

安利博客 liu_runda 有上下界的网络流,顺便抄一段话

有上下界的网络流的核心是”调整”,我们通过一个初始的未必可行的流调整出一个可行流,还可以从可行的未必最大/最小的流调整出最大/最小。
另一个常用技巧是有源汇的流和无源汇的流(循环流)的转换。除了无源汇可行流的求解,其他有源汇的上下界网络流都要用到这个技巧。

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

模型

给定一个网络,求一个流,满足每条边的流量都 $min \leqslant flow \leqslant max$ ,并且每个点都满足 总流入量=总流出量(流量守恒) ,没有源汇。

核心思想

将一个不满足流量守恒的初始流调整成满足流量守恒的流。

方法

如果存在一个可行流,它一定满足每条边的流量都大于等于下界。那么我们可以先令每条边的流量等于它的下界,得到一个初始流,然后建出这个流的残余网络(每条边流量为上下界之差)。初始流不一定满足流量守恒,我们要做的就是通过增加某些边的流量使它流量守恒来得到一个可行流。

我们将之后扩大流量的流叫做附加流,初始流合并附加流就是可行流。那么,为达到流量守恒,一定存在:

  • 如果一个点在初始流中满足流量守恒,那么它在附加流中也满足流量守恒
  • 如果一个点在初始流中的流入量比流出量多 $x$ ,那么它在附加流中流出量比流入量少 $x$
  • 如果一个点在初始流中的流入量比流出量少 $x$ ,那么它在附加流中流出量比流入量多 $x$

我们用 $d[i]$ 表示点 $i$ 在初始流中流入量-流出量的值,那么 $d[i]$ 的正负就可以表示以上三种情况。

如果一个点$d[i] < 0$,我们需要给多出的流入量一个出处,需要让附加流中 $i$ 的流入量比流出量少 $-d[i]$,所以建一条从 $i$ 出发的边,流量为 $-d[i]$;如果 $d[i] > 0$,则
建一条指向 $i$ 的边,流量为$d[i]$

虚拟源汇点 $s$,$t$。分类

为了得到一个可行流,指向 $t$ 的边的总流量上限必须等于从 $s$ 出发的边的总流量上限,因为原图上每条边对两个端点的 $d[i]$ 的贡献一正一负绝对值相同,所以 $\sum_{i=1}^n d[i] = 0$,并且

除了连接 $s$,$t$ 的边以外,在连上原图中的边,流量为上界-下界。在这个图上,如果我们能够找到一个流满足所有连接 $s$,$t$ 的边都满流,那这个流在原图中边上的流量就是我们要的附加流。这样的流就是我们所建的新图中 $s$ 到 $t$ 的最大流。

存在可行流的条件:$s$ 到 $t$ 的最大流 = $\sum_{d[i]>0} d[i]$

最后,每条边的流量 = 下界 + 附加流中它的流量

例题

ZOJ2314 Reactor Cooling

求是否存在一个无源汇可行流,若存在,输出每条边的流量

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;

namespace TYC
{
const int N=210;
const int M=40010;
const int inf=0x3f3f3f3f;

int n,m,cnt,s,t,Head[N],d[N],dep[N],low[M],cur[N];

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

struct edge
{
int to,next,w;
}E[M<<1];

inline void add(const int u,const int v,const int w)
{
E[++cnt]=(edge){v,Head[u],w};
Head[u]=cnt;
E[++cnt]=(edge){u,Head[v],0};
Head[v]=cnt;
}

void init()
{
s=n+1,t=s+1,cnt=1;
memset(d,0,sizeof(int[n+1]));
memset(Head,0,sizeof(int[t+1]));
}

bool bfs()
{
queue<int> q;
memset(dep,0,sizeof(int[t+5]));
dep[s]=1,q.push(s);
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(E[i].w&&!dep[v])
dep[v]=dep[u]+1,q.push(v);
}
}
return dep[t];
}

int dfs(const int u,const int mn)
{
if(u==t||!mn) return mn;
int v,w,used=0;
for(int i=Head[u];i;i=E[i].next)
{
v=E[i].to;
if(E[i].w&&dep[v]==dep[u]+1)
{
w=dfs(v,min(E[i].w,mn-used));
used+=w;
E[i].w-=w,E[i^1].w+=w;
if(used==mn) return used;
}
}
if(!used) dep[u]=-1;
return used;
}

inline int Dinic()
{
int ans=0;
while(bfs()) ans+=dfs(s,inf);
return ans;
}

void work()
{
int T=read();
while(T--)
{
n=read(),m=read();
init();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),l=read(),u=read();
add(x,y,u-l);
low[i]=l;
d[x]-=l,d[y]+=l;
}
int tot=0,last=cnt;
for(int i=1;i<=n;i++)
{
if(d[i]<0) add(i,t,-d[i]);
else if(d[i]>0) tot+=d[i],add(s,i,d[i]);
}
if(Dinic()!=tot) puts("NO");
else
{
puts("YES");
for(int i=3;i<=last;i+=2)
printf("%d\n",low[i>>1]+E[i].w);
}
puts("");
}
}
}

int main()
{
TYC::work();
return 0;
}

有源汇的上下界可行流

模型

给定一个有源点 $s$ 和汇点 $t$ 的网络,求出一个源点流出量=汇点流入量,其它点流量守恒的的流,并且每条边满足上下界限制。

方法

发现只有源汇点流量不守恒,那么我们建一条从 $t$ 到 $s$ 的边上界为 $inf$ 下界为 $0$,把 $t$ 的流出量流入 $s$ 使它俩守恒,就变成了一个无源汇可行流了。

如果是虚拟的源汇点不连可行流的虚拟源汇点

求完后,边 $(t->s)$ 的流量就是源汇点的流量(整个网络的流量)。

代码参见最小流的部分

有源汇的上下界最大流

模型

在上个模块条件下要求总流量最大

方法

上面那个求出来的是可行流,不一定最大,我们在残余网络上跑 $s$ 到 $t$ 的最大流即可。

最大流=可行流流量( $t->s$ 边的流量)+ 新增广的 $s$ 到 $t$ 的最大流

注意 这里的 $s$,$t$是原图中给定的源汇点,不是求可行流时虚拟的源汇点。

要先删除了那两个虚拟的源汇点(删掉和它相连的边)和新加的边 $(t->s)$ (即将边权设为0)再算!!

感觉没啥给代码的必要……(可以参见最小流)

有源汇的上下界最小流

模型

在上上一个模块条件要求下,总流量最小

方法

先跑有源汇可行流,然后在残余网络上跑 $t$ 到 $s$ 的最大流,这样实际上消耗的图中的反向边,反向边流量的减少就是总流量的减少,即缩减流量。

最小流=可行流流量( $t->s$ 边的流量)- 减去的 $t$ 到 $s$ 的最大流

因为这些边的下界并没有在图中建出,即无论怎么减少,只要边的流量还是 $\leqslant 0$ 的,它就依旧满足流量下界。

例题

bzoj2502 清理雪道
luogu4843 清理雪道

画个图一看数据范围这么小,这不就是个流嘛,将总部看作源点,源点可以到达任意点;再将结束看作汇点,任意点都可以到汇点。然后要求每条边至少走一次,那就是边的流量有下界为1,没有上界,求最小次数直接跑有源汇上下界最小流就行了

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;

namespace TYC
{
const int N=110;
const int M=10010;
const int inf=0x3f3f3f3f;

int n,s,t,cnt=1,Head[N],d[N],deg[N],cur[N],dep[N];

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

struct edge
{
int to,next,w;
}E[M<<2];

inline void add(const int u,const int v,const int w)
{
E[++cnt]=(edge){v,Head[u],w};
Head[u]=cnt;
E[++cnt]=(edge){u,Head[v],0};
Head[v]=cnt;
}

bool bfs()
{
queue<int> q;
memset(dep,0,sizeof(int[t+5]));
dep[s]=1,q.push(s);
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(E[i].w&&!dep[v])
dep[v]=dep[u]+1,q.push(v);
}
}
return dep[t];
}

int dfs(const int u,const int mn)
{
if(u==t||!mn) return mn;
int v,w,used=0;
for(int i=Head[u];i;i=E[i].next)
{
v=E[i].to;
if(E[i].w&&dep[v]==dep[u]+1)
{
w=dfs(v,min(E[i].w,mn-used));
used+=w;
E[i].w-=w,E[i^1].w+=w;
if(used==mn) return used;
}
}
if(!used) dep[u]=-1;
return used;
}

inline int Dinic()
{
int ans=0;
while(bfs()) ans+=dfs(s,inf);
return ans;
}

void work()
{
n=read();
int ss=n+1,tt=n+2;
s=n+3,t=n+4;
for(int u=1;u<=n;u++)
{
int k=read();
while(k--)
{
int v=read();
add(u,v,inf);
d[u]--,d[v]++;
}
}
for(int i=1;i<=n;i++)
add(ss,i,inf),add(i,tt,inf);
add(tt,ss,inf);
int ed=cnt;
for(int i=1;i<=n;i++)
if(d[i]>0) add(s,i,d[i]);
else if(d[i]<0) add(i,t,-d[i]);
Dinic();
int flow=E[ed].w;
for(int i=Head[s];i;i=E[i].next) E[i].w=E[i^1].w=0;
for(int i=Head[t];i;i=E[i].next) E[i].w=E[i^1].w=0;
E[ed-1].w=E[ed].w=0;//一定要删了后来加的边
s=tt,t=ss;//跑t->s的最大流
printf("%d\n",flow-Dinic());
}
}

int main()
{
TYC::work();
return 0;
}

因为实在是害怕不小心咕咕咕以至于忘了这码子事(忘到猴年马月),所以今天继续把费用流补上

无源汇上下界最小/大费用可行流

模型

在无源汇上下界可行流的基础上,要求费用最小。

方法

同可行流一样,首先先将下界作为初始流(当然要把费用加上),然后按照上面一样的建图方法,就是边加上费用,其中新加的连接虚拟源汇的边费用为 $0$,跑费用流,得到的就是附加流的最小费用,加上初始流费用就是答案。

有源汇上下界最小/大费用可行流

模型

懒得说了,懂得

方法

一样一样,连 $(t->s)$、上界 $inf$、费用 $0$ 的边,然后就可以跑无源汇上下界最小/大费用可行流了。

例题

luogu 4043 [AHOI2014/JSOI2014]支线剧情
bzoj 3876 [Ahoi2014&Jsoi2014]支线剧情

给你一个有向无环图,每条边有一个费用,要求覆盖所有路径的条件下费用和最小。

看到路径覆盖自然网络流,配合费用就是费用流。然后路径覆盖就是每条边有一个下界为 $1$,没有上界,有源点 $1$ ,就变成了有源汇上下界最小费用可行流了,贴板贴板。

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
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;

namespace TYC
{
const int N=310;
const int M=900010;
const int inf=0x3f3f3f3f;

int n,s,t,ans,Head[N],dis[N],vis[N],d[N],pre[N];

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

struct edge
{
int to,next,w,c;
}E[M<<1];

inline void add(const int u,const int v,const int w,const int c)
{
static int cnt=1;
E[++cnt]=(edge){v,Head[u],w,c};
Head[u]=cnt;
E[++cnt]=(edge){u,Head[v],0,-c};
Head[v]=cnt;
}

bool spfa()
{
queue<int> q;
memset(dis,inf,sizeof(int[t+1]));
memset(pre,0,sizeof(int[t+1]));
dis[s]=0,q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=0;
for(int i=Head[u];i;i=E[i].next)
{
int v=E[i].to;
if(E[i].w&&dis[v]>dis[u]+E[i].c)
{
dis[v]=dis[u]+E[i].c;
pre[v]=i;
if(!vis[v]) vis[v]=1,q.push(v);
}
}
}
return pre[t];
}

void mcmf()
{
while(spfa())
{
int mn=inf;
for(int i=pre[t];i;i=pre[E[i^1].to])
mn=min(mn,E[i].w);
for(int i=pre[t];i;i=pre[E[i^1].to])
E[i].w-=mn,E[i^1].w+=mn;
ans+=mn*dis[t];
}
}

void work()
{
n=read(),s=n+2,t=s+1;
for(int i=1;i<=n;i++)
{
int k=read();
d[i]-=k;
while(k--)
{
int j=read(),val=read();
d[j]++,ans+=val;
add(i,j,inf,val);
}
}
for(int i=2;i<=n;i++) add(i,n+1,inf,0);
add(n+1,1,inf,0);
for(int i=1;i<=n;i++)
if(d[i]>0) add(s,i,d[i],0);
else add(i,t,-d[i],0);
mcmf();
printf("%d\n",ans);
}
}

int main()
{
TYC::work();
return 0;
}

完结撒花~