网络流

网络流,也被称为最大流。

模型也非常简单,就是一个管道系统,在有源点,汇点,和一堆有流速限制的管道连接的情况下,问能从源点到汇点传输流量的最大流速是多少。如下图所示。

Alt text

假定s为源点,t为汇点,中间各箭头为管道,各管道的流速限制均为1。
求最大流的话,很明显,最大流为2。有两条流量:

  • s -> 1 -> 3 -> t,流量为1
  • s -> 2 -> 4 -> t,流量为1

现在是因为图比较简单,我们能一眼看出来。我们自然喜欢程序跑出来的结果是这样。

在程序过程中,自然就是找到一条流量处理一条流量。
如果先找到 s -> 1 -> 3 -> t,然后找到 s -> 2 -> 4 -> t,自然皆大欢喜。
但是如果程序的第一条直接找到 s -> 1 -> 4 -> t 了呢?这样的最终结果就只有一条流量。

为了解决这个问题,有人提出了一种叫回退边(后悔边)的概念。 这个也是本算法的精髓所在。

后悔边:如果我们根据原图建了一条从u到v,流量为f的边 (u,v)=f。 同时,我们也需要建一条从v到u,流量为0的边 (v,u)=0,这条边我们就称为后悔边。(u,v) 和 (v,u)互为反向边。

同时,在程序进行过程中,如果我们如果从残余网络中找到一条从s到v的流量为f,在更新的过程中,我们首先要把最终答案加上c,然后我们不仅要把在该流量上的各边的剩余流量减去f,同时还要把流量上各条边的反向边的流量加上f。

这样做有什么好处呢?

还是以上图为例,如果我们先找到了 s -> 1 -> 3 -> t,流量为1。我们首先在最终答案中加1,然后在更新的过程中不仅要把 (s,1)、(1,4)、(4,t) 这几条边的剩余流量减1, 还要把 (1,s)、(4,1)、(t,4) 的剩余流量加1。

此时的残余网络为:

  • (s,1) = 0, (1,s) = 1
  • (s,2) = 1, (2,s) = 0
  • (1,3) = 1, (3,1) = 0
  • (1,4) = 0, (4,1) = 1
  • (2,4) = 1, (4,2) = 0
  • (3,t ) = 1, (t,3 ) = 0
  • (4,t ) = 0, (t,4 ) = 1

然后我们从残余网络中找流量,发现此时能找到一条 s -> 2 -> 4 -> 1 -> 3 -> t 的流量了!然后我们还按之前的方式更新。再找的时候找不到新的流量了,算法结束。此时的结果是和我们之前用肉眼观察的结果是一样的。

这就是后悔边的神奇之处。

后悔边,顾名思义,就是给了一条边后悔的权利。在算法过程中,原图的边和后悔边是没有区别的,所以找流量的时候也没有任何区别。

这条边存在的意义是,还拿刚刚那条 s -> 2 -> 4 -> 1 -> 3这条流量来说。里面存在一条后悔边(4,1),它的意义是:

  • 之前已经更新过的流量中,有一条从4到t的流量4 -> t,这条流量我可以用到。
  • 目前的残余网络中,还存在一条从1到s得流量1 -> 3 -> t,这条流量可以替换你之前更新过的流量 1 -> 4 -> t
  • 为什么不能你用1 -> 3 -> t,我用4 -> t呢。这样的得到的总流量多一些,我们来交换吧。
  • 你把你的流量退回去,用我给你的。我用你之前的。 至于中间的(4,1),退回去我也用不上,大不了都不用了吧。

这样下来,最佳方案就出现了。

可以发现,在有后悔边存在的情况下,先找哪条流量后找哪条流量就已经不重要了。反正都是可以做修改的。这样的话,只要考虑如何高效地找流量就好了。这个当然不能随便找,有环的话肯定要进入死循环。

Dinic算法中,我们采用了分层图的形式。分层用BFS来实现。

  • 首先,将源点的level设为0,并将源点加入队列。
  • 从队列中取出一个点u,遍历以它为起点还有流量的边,找到点v。如果点v还没被加入队列过,将v的level设为level[u]+1,并将v加入队列。
  • 回到步骤2,直到队列为空。

然后我们规定,level为a的点只能向level为a+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
const int N = 1e5 + 100;
const int M = 1e7 + 100;
const int INF = 1e9;
struct Edge{
int to,next;
int c;
}edge[M];
int head[N], level[N], que[N], ip;
void init() {
memset(head, -1, sizeof(head));
ip = 0;
}
bool makelevel(int s,int t) { //将图分层
memset(level,0,sizeof(level));
int num=0;
que[num++]=s;
level[s]=1;
for(int i=0;i<num;i++) {
int top=que[i];
if(top==t) return 1; //找到t了,后面再找level肯定比t大
for(int k=head[top];k!=-1;k=edge[k].next) {
if(!level[edge[k].to]&&edge[k].c>0) {
que[num++]=edge[k].to;
level[edge[k].to]=level[top]+1;
}
}
}
return 0;
}
int dfs(int now,int maxf,int t) { //从残余网络中找流量
if(now==t) return maxf;
int ret=0;
for(int k=head[now];k!=-1;k=edge[k].next) {
if(edge[k].c>0&&level[edge[k].to]==(level[now]+1)) {
int c=dfs(edge[k].to,min(maxf-ret,edge[k].c),t);
edge[k].c-=c;
edge[k^1].c+=c;
ret+=c;
if(ret==maxf) return ret;
}
}
--level[now]; //一个优化,说明往level[now]+1找流量已经找不到了。自己就降一个level。
return ret;
}
int dinic(int s,int t) {
int ans=0;
while(makelevel(s,t)) ans+=dfs(s,INF,t);
return ans;
}
void add(int u,int v,int c,int f) {//有向边f为0 ,否则为 c
edge[ip].to=v;edge[ip].c=c;edge[ip].next=head[u];head[u]=ip++;
edge[ip].to=u;edge[ip].c=f;edge[ip].next=head[v];head[v]=ip++;
}