EK (Edmond-Karp) 算法 学习笔记

(Updated: )
oi
,

什么是EK算法

EK (Edmond-Karp) 算法，说白了就是求最大流/费用流之类的问题的算法。

什么是最大流

定义

带权的有向图$G=(V,E)$，满足以下条件，则称为网络流图$(flow network)$：

  1. 仅有一个入度为$0$的顶点$s$，称$s$为源点。
  2. 仅有一个出度为$0$的顶点$t$，称$t$为汇点。
  3. 每条边的权值都为非负数，称为该边的容量，记作$c(i,j)$。
  4. 通过容量网络$G$中每条弧$< u,v>$上的实际流量(简称流量),记为$f(u,v)$，称为弧的流量。

简单来说就是水流从一个源点$s$通过很多路径，经过很多点，到达汇点$t$，问你最多能有多少水能够到达$t$点。 从$s$到$t$经过若干个点，若干条边，每一条边的水流都不能超过边权值（可以小于等于但不能大于） （由于是来学EK算法的，最大流什么的详细解读就不说了）

例题

Luogu P3376 【模板】网络最大流

题意

给出一个网络图，以及其源点和汇点，求出其网络最大流。

思路

这是最大流的模板题，请往下阅读。

增广路

增广路定义

增广路是指从源点$s$到汇点$t$的一条路，流过这条路，可以使得当前的流可以增加。

如何求增广路

其实就是从源点$s$开始$bfs$即可，到达汇点$t$时，然后找到这个路径的权值的最小的边，然后把路径上的每一条边减去这个最小值即可。

Code

寻找增广路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
queue<int> q;//队列
bool bfs(){
    while(!q.empty()) q.pop();//清空
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    vis[s]=1;//源点标记
    q.push(s);//入队
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=fir[u];i;i=nxt[i]){
            int to=son[i];
            if(vis[to]==0&&w[i]!=0){
                pre[to].v=u;
                pre[to].edge=i;//记路径
                if(to==t) return 1;//到达t点
                vis[to]=1;
                q.push(to);//拓展
            }
        }
    }
    return 0;
}

定义

1
2
3
4
5
int n,m,s,t,vis[MAXN];
int fir[MAXN],nxt[MAXN],w[MAXN],son[MAXN],tot=1,ans;//领接表
struct edge{
    int v,edge;//用来记路径
}pre[101010];

EK算法核心（你别急，我还没说完）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int EK(){
    ans=0;
    while(bfs()){
        int Min=2e9;
        for(int i=t;i!=s;i=pre[i].v){
            Min=min(Min,w[pre[i].edge]);
        }
        for(int i=t;i!=s;i=pre[i].v){
            w[pre[i].edge]-=Min;
        }
        ans+=Min;
    }
    return ans;
}

这样很明显是错误的。。。

反向边

为什么要建反边

为什么不建反边(逃： 非常显然，如果第一次流错了使其无法得到最大流怎么办？ 就比如这张图：

然而$bfs$沙雕的选了上面一条路怎么办。。。 所以这时候就需要反向边出场了 一开始用反向边建一个比边权为$0$的边。就像这样↓

然后每次$bfs$以后给相应的反边加上流量，正边减去流量。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int EK(){
    ans=0;
    while(bfs()){
        int Min=2e9;
        for(int i=t;i!=s;i=pre[i].v){
            Min=min(Min,w[pre[i].edge]);
        }
        for(int i=t;i!=s;i=pre[i].v){
            w[pre[i].edge]-=Min;//减去流量
            w[pre[i].edge^1]+=Min;//加上流量
        }
        ans+=Min;
    }
    return ans;
}

回归例题

所以这道最大流的模板题代码：

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
119
120
121
122
123
124
125
126
127
128
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
#define MAXN 200010
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
int n,m,s,t,vis[MAXN];
int fir[MAXN],nxt[MAXN],w[MAXN],son[MAXN],tot=1,ans;
struct edge{
    int v,edge;
}pre[101010];
void add(int x,int y,int z){
    ++tot;
    nxt[tot]=fir[x];
    fir[x]=tot;
    w[tot]=z;
    son[tot]=y;
}
queue<int> q;
bool bfs(){
    while(!q.empty()) q.pop();
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=fir[u];i;i=nxt[i]){
            int to=son[i];
            if(vis[to]==0&&w[i]!=0){
                pre[to].v=u;
                pre[to].edge=i;
                if(to==t) return 1;
                vis[to]=1;
                q.push(to);
            }
        }
    }
    return 0;
}
int EK(){
    ans=0;
    while(bfs()){
        int Min=2e9;
        for(int i=t;i!=s;i=pre[i].v){
            Min=min(Min,w[pre[i].edge]);
        }
        for(int i=t;i!=s;i=pre[i].v){
            w[pre[i].edge]-=Min;
            w[pre[i].edge^1]+=Min;
        }
        ans+=Min;
    }
    return ans;
}
int main(){
    n=read();m=read();s=read();t=read();
    for(int x,y,z,i=1;i<=m;i++){
        x=read();y=read();z=read();
        add(x,y,z);
        add(y,x,0);
    }
    write(EK());putchar('\n');
    return 0;
}

EK算法拓展

费用流问题

Luogu P3381 【模板】最小费用最大流

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define int long long 
using namespace std;
#define MAXN 200010
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
int n,m,s,t,vis[MAXN],dis[MAXN],anss;
int fir[MAXN],nxt[MAXN],w[MAXN],son[MAXN],tot=1,ans,cost[MAXN];
struct edge{
    int v,edge;
}pre[101010];
void add(int x,int y,int z,int c){
    ++tot;
    nxt[tot]=fir[x];
    fir[x]=tot;
    w[tot]=z;
    son[tot]=y;
    cost[tot]=c;
}
queue<int> q;
bool spfa(){
    while(!q.empty()) q.pop();
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(dis,63,sizeof(dis));
    dis[s]=0;dis[t]=2e9;
    vis[s]=1;q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(int i=fir[u];i;i=nxt[i]){
            int to=son[i];
            if(w[i]>0&&dis[to]>dis[u]+cost[i]){
                dis[to]=dis[u]+cost[i];
                pre[to].edge=i;
                pre[to].v=u;
                if(vis[to]==0){
                    vis[to]=1;
                    q.push(to);
                }
            }
        }
    }
    if(dis[t]<2e9) return 1;
    return 0;
}
int EK(){
    ans=0;anss=0;
    while(spfa()){
        int Min=2e9;
        for(int i=t;i!=s;i=pre[i].v){
            Min=min(Min,w[pre[i].edge]);
        }
        for(int i=t;i!=s;i=pre[i].v){
            w[pre[i].edge]-=Min;
            w[pre[i].edge^1]+=Min;
        }
        anss+=Min;
        ans+=Min*dis[t];
    }
    return ans;
}
signed main(){
    n=read();m=read();s=read();t=read();
    for(int x,y,z,c,i=1;i<=m;i++){
        x=read();y=read();z=read();c=read();
        add(x,y,z,c);
        add(y,x,0,-c);
    }
    EK();
    write(anss);putchar(' ');
    write(ans);putchar('\n');
    return 0;
}