网络流之最大流

算法

相关的介绍

描述

在满足网络流的性质的情况下，从源点s到汇点t的最大流量

网络流的三个性质

1、容量限制: f[u,v]<=c[u,v]
2、反对称性：f[u,v] = - f[v,u]
3、流量平衡: 对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。

有关于网络流的几个名词

残余网络：对于某一条边还能再有多少流量经过（r(u,v) = c(u,v) – f(u,v)）;
增广路：在残余网络中的一条从s通往t的路径且对于任意一条（u,v）都有r(u,v)>0;
最小割：对于图中的两个点(一般为源点和汇点)来说，如果把图中的一些边去掉，如果它们之间无法连通的话，则这些边组成的集合就叫为割了。如果这些边有权值，最小割就是指权值之和最小的一个割。
最大流和最小割：应用于网络中，指总流量不超过链路可承载的最大值，且在每条子路径上取尽可能少的流量。对任意一个只有一个源点一个汇点的图来说，从源点到汇点的最大流等于最小割。

总结

关于网络流学习了dinic算法，感觉上代码并不复杂但是理解起来需要一定的时间。
dinic算法先使用bfs进行图的分层即求出图中的每一个点到s的最小边数，以边数是否相等来建立图层，并接着在层次图上进行增广路算法，且对于每一条路径，其上面的任意两个点都不可能属于同一图层，接下来就是重复进行分层与增广直至不能增广为止。
网络流的题目与二分图的题目有着异曲同工之妙，在我看来它们的难点都是在如何建立图上面，比如POJ的3281就需要在食物和水之间插入牛的顶点，而且为了防止一牛对多食物和水的情况还进行了对牛顶点的拆分，这样的脑洞需要对题的深刻分析，我认为需要好好看看如何建图.

代码

源于FZ

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
const int NV=20005;
const int NE=500005;
int he[NV],ecnt;
int src,sink;
struct edge
{
    int v,next,f;
} E[2*NE];
void adde(int u,int v,int c)
{
    E[++ecnt].v=v;
    E[ecnt].f=c;
    E[ecnt].next=he[u];
    he[u]=ecnt;
    E[++ecnt].v=u;
    E[ecnt].f=0;
    E[ecnt].next=he[v];
    he[v]=ecnt;
}
void init()
{
    ecnt=0;
    memset(he,-1,sizeof(he));
}
queue<int> que;
bool vis[NV];
int dis[NV];
void bfs()
{
    memset(dis,0,sizeof(dis));
    while(!que.empty()) que.pop();
    vis[src]=1;
    que.push(src);
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        for (int i=he[u]; i!=-1; i=E[i].next)
            if (E[i].f&&!vis[E[i].v])
            {
                que.push(E[i].v);
                dis[E[i].v]=dis[u]+1;
                vis[E[i].v]=1;
            }
    }
}
int dfs(int u,int delta)
{
    if (u==sink)
        return delta;
    else
    {
        int ret=0;
        for (int i=he[u]; delta&&i!=-1; i=E[i].next)
            if (E[i].f&&dis[E[i].v]==dis[u]+1)
            {
                int dd=dfs(E[i].v,min(E[i].f,delta));
                E[i].f-=dd;
                E[(i+1)^1-1].f+=dd;
                delta-=dd;
                ret+=dd;
            }
        return ret;
    }
}
int maxflow()
{
    int ret=0;
    while(1)
    {
        memset(vis,0,sizeof(vis));
        bfs();
        if (!vis[sink]) return ret;
        ret+=dfs(src,inf);
    }
}