说在前面

其实很早以前就知道有这个网络流算法了，而且据说是特别难的（毕竟当时我连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
49
#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;
}