网络流-最大流求解

说在前面

其实很早以前就知道有这个网络流算法了,而且据说是特别难的(毕竟当时我连DP和图论都在仰望中)现在接触到了,很神奇,但是并没有想象中的那么难 (毕竟可以背模板)

这一篇主要是我最网络流的最大流的理解以及在求最大流的时候的Ford-Fulkerson算和Dinic算法。

网络流

网络流概念:

什么是网络?网络其实就是有向带权图。为什么要叫网络,是因为权值是容量,容量意味着可以在单位时间内经过的上限,但是可以比上限小。比如说我们一个运输的管道,每段管道都有一个最大水量,如果超出了这个最大水量,就会爆开水管,而这个运输管道系统就是一个网络流。

最大流:

寻找网络G上可能的最大流量(和一个有最大流量的可行流方案),即为网络G上的最大流问题。

增广路径

增广路径(可改进路径)的定义:

若P是网络中连结源点s和汇点t的一条路,我们定义路的方向是从s到t,则路上的弧有两种:

  • 前向弧—弧的方向与路的方向一致。前向弧的全体记为P+;
  • 后向弧—弧的方向与路的方向相反。后向弧的全体记为P-;

设F是一个可行流,P 是从s到t的一条路,若P满足下列条件:

  • 在P+的所有前向弧(u,v)上,0≦f(u,v) < C(u,v);
  • 在P-的所有后向弧(u,v)上,0<f(u,v) ≦C(u,v);

则称P是关于可行流F的一条可增广路径。

上图中的S-A-C-B-D-E-T 为一增广路径。其中(C,B)为后向弧,其它为前向弧。

残留网络

由于要考虑前向弧、后向弧,分析、描述时不简洁,在图上直观看也不容易看出增广路径。因此我们把已经有的流量从容量中分离出来表示,引入一个与原问题等价的附加网络:残留网络。

那么我们就可以将图进行一下改进:

在这张图上,我们找增广路径显的非常直观了!

最大流求解

最大流定理:
如果残留网络上找不到增广路径,则当前流为最大流;反之,如果当前流不为最大流,则一定有增广路径。

Ford-Fulkerson算法

算法讲解:

对于Ford-Fulkerson算法来说无论是理解方面还是代码实现,都是非常简单的,但是这种简单也决定了它效率并不是很高,至少是要比Dinic要低一些的。所以说还是要练习好Dinic算法。

Ford-Fulkerson算法核心就是不听的寻找增广路径,不过然后利用一个Forward来记录下来这个路径的最小增加流,然后加到最终答案all中,并且利用这个Forward来更新路上的所有路径的值,也就是一个前向弧和一个后向弧(一个减,一个加)。这样不停地找直到没有办法找到增广路径为止。

Ford-Fulkerson用邻接矩阵的代码是非常少的,但是相对应的空间和时间的复杂度都会提高(指的是常数),所以最好还是用邻接表(QAQ如果数据的范围比较少的话直接上邻接矩阵的Ford-Fulkerson)

更重要的是,Ford-Fulkerson算法可能会被某些丧心病狂的老师卡掉(毕竟简单好写),而Ford-Fulkerson算法就是通过边权进行修改的,那么如果构成一条路的边权非常大,而另外一条边比较小,则会更新非常多次,所以更加证明了要去学Dinic算法。

比如下图:

我们知道,Ford-Fulkerson算法是每次找到一条增广路径,
这个图中如果用Ford-Fulkerson算法,b—c这条边的退流将会做1000次,极大的影响算法的效率。一定要提防某些丧心病狂的老师!!!具体为什么会退流1000次可以模拟计算一下;

在读入数据的时候一定要记得可能会出现重边的现象,这就和图不一
定是联通的道理一样的。

代码:

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,dis[400][400];
int x,y,z,all,Forward;
bool Get=true,vis[400];
void DFS(int x,int Line)
{
vis[x]=true;
if(x==n)
{
Get=true;
all+=Line;
Forward=Line;
return;
}
for(int i=1;i<=n;i++)
if(dis[x][i]>0&&!vis[i])
{
DFS(i,min(dis[x][i],Line));
if(Get)
{
dis[x][i]-=Forward;
dis[i][x]+=Forward;
return;
}
}
}
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
dis[x][y]+=z;//有可能出现重边
}
while(Get)
{
Get=false;
memset(vis,false,sizeof(vis));
DFS(1,123456789);
}
cout<<all<<endl;
return 0;
}

Dinic算法

写在前面:

果然网络流不愧是高级算法啊,整整用了三节课,才弄懂Dinic算法,其实是讲稿写的并不清楚!!!

网络流真的是很神奇啊 (好像我每个算法都是这么说的)

算法讲解:

Dinic算分和Ford-Fulkerson的主要区别就是Dinic算法是在Ford-Fulkerson算法里面,是每次一单独进行寻找增广路的,但是在Dinic里面,因为需要进行将图中的所有增广路都跟新掉,所以是进行分层操作,然后将一张图根据访问时间进行区分层次。这里分层的目的有两个: (以下为我的个人理解可能不对)

第一个就是通过进行分层来查看是否还存在有增广路,其次就是通过分层来防止DFS的死循环。因为在Dinic算法里面,我们进行的DFS的过程中,是需要更新所有的增广路,所以就可以重复的访问某一条边,但如果出现环的情况,就会死循环,那么为了防止这种情况的产生就需要进行分层。而普通的进行bool类型的vis数组标记是没有办法实现的。

我们进行分层之后,每次选择走的路都是一条最短的路,这样相对来说可以更新的流更大些,提高算法运行速度。

然后就是进行DFS更新利用MAXFlow来记录下来自己这里可以通过流量的当前最大值,然后Flow是可以分给下一个人的最大流量,如果找到了汇总点,那么我们就求出了这条增广路所能增广的最大值,将它加到MaxFlow里面,如果自己能够提供的流量,也就是min(上一个人给自己的流量,自己本身最大的流量)等于了MaxFlow我们就可以进行剪枝了,因为下面已经不可能再通过任何多余的流了。

最后返回可增广的最大流的时候判断一下,如果为零,那么以后也不可能再增广了,就不需要访问他了,那么直接将分层标记改为-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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
struct Edge
{
int Point;
int Value;
int Back;
int Next;
}a[2000];
int n,m,x,y,z,len,Queue[400];
int Link[500],Level[400],all;
bool GetLevel()
{
memset(Level,-1,sizeof(Level));
int head=0,tail=1;
Queue[1]=1; Level[1]=0;
while(++head<=tail)
{
for(int i=Link[Queue[head]];i;i=a[i].Next)
if(Level[a[i].Point]<0&&a[i].Value)
{
Queue[++tail]=a[i].Point;
Level[Queue[tail]]=Level[Queue[head]]+1;
}
}
return Level[n]>=0;
}
int GetMaxFlow(int x,int Flow)
{
if(x==n) return Flow;
int MaxFlow=0,D=0;
for(int i=Link[x];i&&MaxFlow<Flow;i=a[i].Next)
if(a[i].Value&&Level[a[i].Point]==Level[x]+1)
if(D=GetMaxFlow(a[i].Point,min(Flow-MaxFlow,a[i].Value)))
{
MaxFlow+=D;
a[i].Value-=D;
a[a[i].Back].Value+=D;
}
if(!MaxFlow) Level[x]=-1;
return MaxFlow;
}
void Dinic()
{
int ans;
while(GetLevel())
while(ans=GetMaxFlow(1,123456789)) all+=ans;
}
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
a[++len].Point=y;
a[len].Next=Link[x];
a[len].Back=len+1;
a[len].Value=z;
Link[x]=len;
a[++len].Point=x;
a[len].Next=Link[y];
a[len].Back=len-1;
a[len].Value=0;
Link[y]=len;
}
Dinic();
cout<<all<<endl;
return 0;
}