EK (Edmond-Karp) 算法 学习笔记
|
789
|
1
|
oi
|

1031 字
|
19 分钟
本文最后更新于 1019 天前，其中的信息可能已经有所发展或是发生改变。

什么是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

寻找增广路

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;
}

定义

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算法核心（你别急，我还没说完）

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

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

#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

#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;
}
EK算法学习

评论

  1. sky casino ad song
    3年前
    2019-4-20 22:06:40

    I will immediately seize your rss feed as I can’t to find your
    e-mail subscription link or newsletter service.
    Do you’ve any? Please permit me recognise in order that I could subscribe.

    Thanks. http://www.epowersports.com/media/js/netsoltrademark.php?d=microscan.net%2F__media__%2Fjs%2Fnetsoltrademark.php%3Fd%3D918.network%2Fcasino-games%2F76-sky777

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
POJ List

							
							

							
CF377D Developing Game

							
							

							
CF878E Numbers on the blackboard

							
							

							
CF1179D Fedor Runs for President

							
							

							
P6072 『MdOI R1』Path

							
							

							
「NOIP2021模拟赛8.19 C」玩家（gamer）

							
							

							
P3349 [ZJOI2016]小星星

							
							

							
浅谈容斥原理

							
							

							
义乌中学暑假集训 2021.07.16 D

							
							

							
义乌中学暑假集训 2021.07.15 D