源码:

Network-flows by pascal

最容易懂的属于你的网络流…

What is “Network-flows”?

网络流的定义?肯定很多人士看了第一眼,就会觉得:
什么鬼呀！


假设这张图

我有无数个汽车,我要从4点到3点,并且每一条路的流量(相当于边权吧)是它可以的通车数量。

并且通过了一定车就只能通流量减去通车量那么多的车了(例子:4到3有20辆车通过后,那么这条路同等于封死了,如果只是通过10辆,那么还有10辆车可以通过)

那么,请求出我有多少辆车可以过去?

1
2
3
4
5
聪明的你选择了如下方案:

1. 4->3,20辆车
2. 4->2->3,20辆车 (为什么,4->2不是30辆吗? 拜托,你到2->3的时候就只有20辆车了) (注意,此时的4->2只有10流量了)
3. 4->2->1->3,10辆车 (又为什么? 拜托,4->2只有10啦!)

把我们的方案变成图:

我告诉你,红色的边代表我们选的边,灰色暂时不用管,flow是我们的流量总值(就是答案啦)。

这就是:神奇的网络流

基础

我们介绍EK和Dinic算法。

首先,我们了解什么叫做增广路。

增广路

在众多种方案中(路线),我们对可行的路线(也就是>0)进行增广。

如图:

这就是增广。

你会想,这不是简单吗,我们一个一个回溯,跑big法师或者大法师不就行了?(Dfs,Bfs)

我们会出现一种很坑的情况。
如图:

太棒了!

反向边

这就是这个算法的精华部分，利用反向边，使程序有了一个后悔和改正的机会。

盗了图:

反向边这个东西想深刻理解很难,按照我的理解方式:

1
2
反正被选过了,反向没有什么关系,还能有反悔机会,而且是流量,又不是什么最短路径,而且能AC,真是太棒了...
(真是蒟蒻了)

当此边被选的时候,建立反向边,直接把反向边增加为流走流量就可以了(table[A][B]减去流走流量,table[B][A]增加流走流量)

我们的两个算法:EK和Dinic都是依靠增广路和反向边的性质来做的呢。

EK (Edmonds_Karp)

建议先抄标,再理解。

1
2
3
4
步骤:
1.从source(源点)出发,用BFS那找出 [ 一条 ] 增广路。(退出BFS)
2.将这些增广路增广并建造反向边。
3.重复source,直到没有增广路找得到。

CODE

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
// 邻接表RE,70分
Uses math;//神奇数学

var
        sink,source,n,m,i,x,y,sum,ans:longint;//sink=汇点,source=源点
        table:array[1..3000,1..3000] of longint;
        last,flow:array[1..100000] of longint;//我们是找到一条增广路才进行增广和反向边,所以要last记录前继点,也就是 什么点到了i这个点=last[i]。flow用来记录到某个点的最大flow值

Function Bfs:longint;//Bfs部分
var
        head,tail,i,k:longint;
        will:array[1..100000] of longint;//队列
begin
        for i:=1 to n do
                last[i]:=-1;
        last[source]:=0;//这个应该懂

        head:=1;
        tail:=1;
        will[1]:=source;
        flow[source]:=maxlongint;//这个也是

        while head<=tail do
        begin
                k:=will[head];
                inc(head);
                if k=sink then//到达汇点,立马结束!
                        break;

                for i:=1 to n do
                        if (table[k,i]>0)and(last[i]=-1) then//找到新点
                        begin
                                last[i]:=k;
                                flow[i]:=min(table[k,i],flow[k]);

                                inc(tail);
                                will[tail]:=i;
                        end;
        end;

        if last[sink]=-1 then//找不到??
                exit(-1);
        Bfs:=flow[sink];//这一条路径的flow
end;

Procedure Edmonds_Karp;
var
        increase,k:longint;
begin
        increase:=Bfs;
        while increase<>-1 do
        begin
                k:=sink;
                while k<>source do
                begin
                        dec(table[last[k],k],increase);//减少正向边
                        inc(table[k,last[k]],increase);//增加反向边(建造)
                        k:=last[k];//继续
                end;
                inc(ans,increase);//增加答案
                increase:=Bfs;//increase用来存储这条边的最大流量
        end;
end;

begin
        read(m,n,source,sink); //主程序才是一个程序最难理解的地方!
        for i:=1 to n do
        begin
                read(x,y,sum);
                inc(table[x,y],sum); //必须inc!!
        end;
        Edmonds_Karp;
        writeln(ans);//才怪
end.

Dinic

我们想,能不能改进EK,少做一点BFS??? (我说:不行!EK万岁!)

那你就[踏]错特错了。

Dinic引入分层图思想,也就是说,这个点离源点多长(经过多少个边),那它就被分在第与源点的距离+1层,在程序中,相同的层不能增广(选择)!

用什么分层?BFS!!

Dinic还有一个好地方,就是一次不止找一个增广路!!!
我们用到DFS!!!

我们每一次循环先分层,再Dfs找增广路。

拓展:当前弧优化(可以自行查找博客)。

CODE

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
Uses math;//神奇的数学

var
        next,reach,value,cnt:array[-1..200000] of longint; //这次我用到了链式前向星,不会的请认真学习 
        dep:array[0..200000] of longint;//分层,深度
        will:array[1..200000] of longint;//队列
        cur:array[1..200000] of longint;//当前弧优化
        n,m,sink,source,i,x,y,sum,tot,maxflow:longint;

procedure add(x,y:longint);//链式前向星
begin
        inc(tot);
        reach[tot]:=y;
        value[tot]:=sum;
        next[tot]:=cnt[x];
        cnt[x]:=tot;
end;

function Bfs:boolean;//分层
var
        head,tail,now,i:longint;
begin
        fillchar(dep,sizeof(dep),0);//清空为0
        dep[source]:=1;
        head:=1;
        tail:=1;
        will[1]:=source;

        while head<=tail do//Bfs队列开始
        begin
                now:=will[head];
                inc(head);
                i:=cnt[now];
                while i<>-1 do
                begin
                        if (value[i]>0)and(dep[reach[i]]=0) then//没有被赋值Dep
                        begin
                                dep[reach[i]]:=dep[now]+1;//You know
                                inc(tail);
                                will[tail]:=reach[i];
                        end;
                        i:=next[i];
                end;
        end;

        if dep[sink]=0 then
                exit(False);//不能分层,汇点没有被赋值
        Bfs:=True;
end;

function Dfs(now,now_flow:longint):longint;//now为现在点,now_flow为现在的流量(最优)
var
        flow,i,flow_,now_flow_:longint;
begin
        flow:=0;
        flow_:=0;
        now_flow_:=now_flow;
        if now=sink then
                exit(now_flow);

        i:=cur[now];
        while i<>-1 do
        begin
                if (dep[reach[i]]=dep[now]+1)and(value[i]>0) then//我说过了,必须同一层! 而且要有连边才行value[i]>0
                begin
                        flow:=Dfs(reach[i],min(now_flow_,value[i]));//神奇的大法师?
                        if flow>0 then
                        begin
                                dec(value[i],flow);
                                inc(value[i xor 1],flow);
                                inc(flow_,flow);//对比EK优化之处
                                dec(now_flow_,flow);//对比EK优化之处
                                if now_flow_=0 then//同上
                                        break; 
                        end;
                end;
                i:=next[i];
        end;
        exit(flow_);//加上本边后最优的流量
end;

procedure Dinic;
var
        tmp,i:longint;
begin

        while Bfs do//如果还能分层(增广)
            while 1<2 do//大佬式优化
            begin
                    for i:=1 to n do
                            cur[i]:=cnt[i];//当前弧优化
                    tmp:=dfs(source,maxlongint);//这一次整个图增广的流量
                    if tmp=0 then
                            break;
                    inc(maxflow,tmp);//answer
            end;
end;

procedure Read_;
begin
        read(n,m,source,sink);
        filldword(cnt,sizeof(cnt) div 4,maxlongint*2+1);//清空数组filldword(数组名字,sizeof(数组名字) div 4,maxlongint*2+1);=变为-1
        filldword(next,sizeof(next) div 4,maxlongint*2+1);
        for i:=1 to m do
        begin
                read(x,y,sum);//链式前向星
                add(x,y);
                dec(sum,sum);
                add(y,x);
        end;
end;

begin
        tot:=1; //必须必须必须必须,以正式的惨案告诉你们:极限数据AC,普通数据WA
        read_;//输入
        Dinic;
        writeln(maxflow);//answer
end.

为了伟大的OI事业!!