发表更新OI笔记19 分钟读完 (大约2812个字)

网络最大流

任意一条网络流边可以描述为$x=(u,v,cap,flow)$。其中$u$为边的起点，$v$为边的终点，$cap$为流量限制，$flow$为当前流量……

网络流简介 （来自OI Wiki）

一 基础内容

任意一条网络流边可以描述为$x=(u,v,cap,flow)$。其中$u$为边的起点，$v$为边的终点，$cap$为流量限制，$flow$为当前流量。

  • 反向边：对于任意一条有向边$e=(i,j,cap,flow)$，定义$e’=(j,i,0,-flow)$ 为它的反向边。注意，反向边在网络流图中是不真实存在的，它其实是一个反悔机制，因此它的流量限制为$0$。定义反向边的当前流量与其对应的正向边的当前流量互为相反数。

反向边图解，图片来自网络：
1.2
图中，选择$u\to v$和$p\to v\to u\to q$两条增广路径，实际上等同于选择$u\to q$和$p\to v$两条增广路径。因为路径$u\to v$和它的反向边$v\to u$的流量之和总为$0$，同时被选中，则意味着这条边对实际流量其实是没有贡献的（这两条边的贡献等于流量之和，等于$0$）。实际上就变成了这两条边同时不被选中。

  • 残量网络：对于图上的任意一条边（包括反向边），定义它们的流量限制与当前流量之差为其残量。一张网络流图上所有边的残量构成残量网络。

  • 增广路：一条从原点（$s$）到汇点（$t$）的路径，并且这条路径上每条边（包括反向边）的残量均大于$0$。设$f_i$为这条路上最小的残量，那么这条增广路可以使得当前流量增加$f_i$。

  • 增广路定理：一张网络流图的流量达到最大流当且仅当残量网络中不存在增广路。

  • 最大流最小割定理：一张网络流图的最大流永远等于该图的最小割的总容量（蒟蒻的我不会证明）。对于割的定义，可以参考割点。

二 Edmond Karp算法

1 流程

于是我们可以得出最朴素的最大流算法（Edmond Karp，EK算法）。

从原点开始，每次找一条到汇点的增广路径，并进行一次增广。

从原点出发向汇点搜索，设$m_i$为$s\to i$这条路上的最小残量$i$，$cap_e$为当前入边（$e$）的流量限制，$flow_e$为当前入边的当前流量，可以得到递推式如下：
$$ m_i = \min m_j,cap_e-flow_e | e=(j,i),e \in E $$

每次到达汇点，将答案增广$m_t$，一直到残量网络中不存在增广路。于是就可以达到最大流。

注意反向边的储存。边表存图时，定义正向边编号为偶数，它的下一条边就是它的反向边。编号从$0$开始，则$i \text{xor} 1$总为$i$的对应边（正向边对应到反向，反向边对应到正向）。

2 实现

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
using namespace std;

const int CP=1e4+4;
const int CE=2e5+5;
const int INF=0x7f7f7f3f;

//边表
class fs{
  public:
      int from,to; //起点，终点
      int cap,flow; //cap容量上限，flow当前流量量
      void init(int f,int t,int c,int fl){
        from=f;
        to=t;
        cap=c;
        flow=fl;
      }
}E[CE];
vector<int> cde[CP]; //节点i的第j条边在E中的序号
int ecnt=0;
void add(int f,int t,int c){
    E[ecnt].init(f,t,c,0);
    E[++ecnt].init(t,f,0,0);  //反向边
    ++ecnt;
    cde[f].push_back(ecnt-2);
    cde[t].push_back(ecnt-1); //反向边
}

int n,m,s,t;

//edmonds karp    
int imp[CP]; //从起点出发的最小残量
int p[CP]; //搜索树上进入节点的边的编号 
    
int Augment(int s,int t)
{
    memset(imp,0,sizeof(imp));
        
    queue<int>Q;
    Q.push(s);
    imp[s]=INF;
        
    while(!Q.empty())
    {
        int cur=Q.front();
        Q.pop();
            
        for(int k=0; k<cde[cur].size(); k++) //遍历边表
        {
            fs e=E[ cde[cur][k] ];
                
            if(!imp[e.to] && e.cap > e.flow)
            {
                p[e.to]=cde[cur][k];
                imp[e.to] = min(imp[cur], e.cap-e.flow); //满足比起点的残量小 
                Q.push(e.to);
            }
         }
    }
        
    return imp[t];
}
int ek(int s,int t)
{
    int maxf=0;
    int aug=0;
    while(aug=Augment(s,t)) //增广到无法增广为止
    {
        for(int cur=t; cur!=s; cur=E[p[cur]].from) //倒着搜索图
        {
            E[p[cur]].flow += aug;
            E[p[cur]^1].flow -= aug; //反向边
           }
           maxf+=aug;
    }
    return maxf;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    while(m--)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
    }
    
    printf("%d",ek(s,t));
    
    return 0;
}

三 Dinic算法

在稠密图中，dinic算法的复杂度要比EK高到不知道哪里去了。

1 思想

dinic的主要思想是把一张网络流图分层，每次只往更深一层寻找增广路，以避免在同一层中绕圈子（这多半是无意义的）。
每当分层图中找不到增广路，这意味着当前图中至少有一条边的流量已经达到限制。也就是说这条边“断了”。而一条断了的边会改变图的分层情况，所以这时重新分层，并继续寻找增广路。
直到图上找不到一条$s\to t$的可行路径。也就是说所有道路都断了。此时会在图上会表现为找不到汇点的所在层级，因为根本没有到达汇点。说的更透彻一点，此时实际上是最小割被完全切断（最大流最小割定理）。

使用bfs完成图的分层，利用dfs寻找增广路径。

2 实现

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

const int CP=1e4+4;
const int CE=2e5+5;

const int INF=0x7f7f7f3f;

//边表
class fs{
  public:
    int to,nxt; //终点和下一条边的编号
    int cap,flow; //cap限制，flow当前流
    fs() {cap=flow=to=0; nxt=-1;} //初始化为-1，因为边的下标从0开始
    void init(int t,int n,int c,int f){
        to=t; nxt=n; cap=c; flow=f;
    }
}E[CE];
int hd[CP],ecnt;
void E_init(){
    memset(hd,-1,sizeof(hd));
    ecnt=0;
}
void _add(int x,int y,int z){
    E[ecnt].init(y,hd[x],z,0);
    hd[x]=ecnt++;
}
void add(int x,int y,int z){
    _add(x,y,z);
    _add(y,x,0); //反向建边
}

//variable define
int n,m,s,t;

//dinic
int dep[CP]; //节点深度

bool build(int s,int t) //bfs
{
    memset(dep,0,sizeof(dep)); //首先清零
    dep[s]=1; //原点深度为1
    
    queue<int>Q;
    Q.push(s);
    
    while(!Q.empty()) //广搜
    {
        int u=Q.front();
        Q.pop();
        
        for(int k=hd[u]; k!=-1; k=E[k].nxt) //遍历边表
        {
            fs e=E[k];
            
            if(e.cap-e.flow>0 && !dep[e.to]) //当前边没有断，且终点没被分层
            {
                Q.push(e.to); 
                dep[e.to]=dep[u]+1; //那么就给终点分层
            }
        }
    }
    
    return dep[t]>0; //判断汇点的深度是不是初始值
}
int Augment(int u,int t,int rst) //dfs :u 节点编号，rst 找到的最小残量
{
    if(u == t) //已经到了汇点
        return rst; //直接返回找到的最小残量
        
    for(int k=hd[u]; k!=-1; k=E[k].nxt) //遍历边表
    {
        fs e=E[k];
        
        if(e.cap-e.flow>0 && dep[u]==dep[e.to]-1) //还有残量，并且在下一层
        {
            int f=Augment(e.to,t, min(rst, e.cap-e.flow)/*从两个残量里面选一个小的*/); 
            if(f) //能增广则增广，因为反向边保留了退路
            {
                E[k].flow+=f;
                E[k^1].flow-=f; //反向边
                return f; //继续向上层递归返回增广量
            }
        }
    }
    return 0; //增广失败
}

int dinic()
{
    int max_flow=0,f;
    while(build(s,t)) //直到所有路径被切断
        while(f=Augment(s,t,INF)) //直到不能增广（此处赋值语句兼用作判断真值），注意这里最小残量的初始值
            max_flow+=f; //加上增广得到的解
    return max_flow;
}

int main()
{
    E_init();
    
    scanf("%d%d%d%d",&n,&m,&s,&t);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    
    printf("%d",dinic());
    
    return 0;
}

3 优化

3-1 多路增广

上文中的代码一次搜索仅找出一条增广路，这样可能会在搜索时走很多重复的道路，造成一些常数负担。

所以每次在一条路上增广时，同时寻找多条增广路，直到干路的最小残量被用完或到达汇点时为止。这样可以避免重复走一条干路。
也就是说，一次dfs搜索所有的增广路。

3-2 当前弧优化

多路增广后，一条仍有残量却已经被增广的边是不可能继续被增广的，因为它所有的增广可能性已经被全部枚举了。所以继续dfs时，不需要再考虑这些边。所以设$cur_i$为新的边表表头，即以$i$为起点且没有被增广过的第一条边的编号，每次增广后更新$cur_i$即可。
注意，每次重新构造分层图后，$cur_i$需复原，因为此时对于 任意一条边 的 任意一种增广可能性 都没有考虑。

3-3 实现

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
119
120
121
122
123
124
125
126
127
128
129
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

const int CP=1e4+4;
const int CE=2e5+5;

const int INF=0x7f7f7f3f;

//边表
class fs{
  public:
    int to,nxt,cap,flow;
    fs() {to=cap=flow=0; nxt=-1;}
    void init(int t,int n,int c,int f){
        to=t; nxt=n; cap=c; flow=f;
    }
}E[CE];
int hd[CP],ecnt=0;
int cur[CP]; //当前弧优化，用来保存从i出发未增广的第一条边在边表中的下标
void E_init(){
    memset(hd,-1,sizeof(hd));
    ecnt=0;
}
void _add(int x,int y,int z){
    E[ecnt].init(y,hd[x],z,0);
    hd[x]=ecnt++;
}
void add(int x,int y,int z){
    _add(x,y,z);
    _add(y,x,0); //反向边
}

//variable define
int n,m,s,t;

void copy(int* a,int* b,int lenth){ //复制a[]到b[]中
    for(int i=0;i<=lenth;i++)
        b[i]=a[i];
}

//dinic
int dep[CP];

bool build(int s,int t) //构造分层图
{
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    
    queue<int>Q;
    Q.push(s);
    
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        
        for(int k=hd[u]; k!=-1; k=E[k].nxt)
        {
            fs e=E[k];
            
            if(!dep[e.to] && e.cap-e.flow>0)
            {
                dep[e.to]=dep[u]+1;
                Q.push(e.to);
            }
        }
    }
    
    return dep[t]>0;
}

int Augment(int u,int t,int rst) //多路增广
{
    if(u == t) //到达汇点
        return rst; //返回最小残量
    
    int used=0; //已经得到的增广量
    for(int k=cur[u]; k!=-1; k=E[k].nxt) //当前弧优化
    {
        cur[u]=k; //重新记录第一条边，赋值为k是因为这条边目前为止还未增广
        fs e=E[k];
        
        if(dep[e.to]==dep[u]+1 && e.cap-e.flow>0)
        {
            int f=Augment(e.to,t, min(rst-used, e.cap-e.flow));
            if(f)
            {
                used+=f; //累加增广量
                E[k].flow+=f;
                E[k^1].flow-=f;
                if(used == rst) //增广路的残量用完了
                    return used; //返回增广量
            }
        }
    }
    
    return used; //搜索完毕，返回增广量
}
int dinic()
{
    int max_flow=0;
    while(build(s,t))
    {
        copy(hd,cur,n); //复制cur的初始边
        max_flow += Augment(s,t,INF); //一次完成所有增广
    }
    return max_flow; 
}

int main()
{
    E_init();
    
    scanf("%d%d%d%d",&n,&m,&s,&t);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    
    printf("%d",dinic());
    
    return 0;
}

网络最大流

https://big-news.cn/2019/02/23/网络最大流/

作者

ce-amtic

发布于

2019-02-23

更新于

2023-04-15

许可协议

CC BY-NC-SA 4.0

#

评论

目录

推荐阅读

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×