首先,如果一个流的残量网络里面没有可行流,那么这个流就是最大流。
EK算法就是基于这个事实的算法,时间复杂度为$O(nm^2)$(n为点数m为边数)。
详细地讲,过程如下:
- 1、找增广路
- 2、更新残量网络增广路上的流量
- 3、重复执行1、2直到网络里没有增广路
对于边与反向边的话,我们使用“成对存储”的技巧来存,这样访问反向边就很方便了。
然后找增广路的过程中需要记录经过的边,以便于之后更新。
请注意cnt初值为1,极其容易写错。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=1e3+5,M=2e4+5,INF=1e9; //因为我们维护残留网络,所以要建反向边,边数*2
int n,m,s,t; //点数,边数,源点,汇点
int head[N],to[M],nxt[M],val[M],cnt; //链式前向星
int pre[N],inc[N],maxflow;
//pre[i]表示bfs里,到点i的边的编号
//inc表示源点到当前点的流量
//maxflow即最大流
bool vis[N]; //记录点有没有被访问过
void add(int u,int v,int w) { //链式前向星加边
to[++cnt]=v;
val[cnt]=w;
nxt[cnt]=head[u];
head[u]=cnt;
}
bool bfs() { //找一条增广路
memset(vis,0,sizeof(vis)); //清空vis数组
queue<int> q; //bfs的队列
q.push(s);
inc[s]=INF; //源点的流量即无穷大
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]) {
int v=to[i],w=val[i];
if(w>0 and !vis[v]) { //边权大于0(即增广路)
inc[v]=min(inc[u],w); //流量为边权与inc[u]的最小值(可以理解为一部分水流被这条管道挡住了)
q.push(v);
vis[v]=true;
pre[v]=i; //记录前向边
if(v==t) //有增广路了
return true;
}
}
}
return false; //找不到增广路
}
void update() {
int p=t; //由于我们是反向存边,所以说需要从汇点往源点走
while(p!=s) {
val[pre[p]]-=inc[t]; //残量网络的定义
val[pre[p]^1]+=inc[t]; //i^1即i的反向边
p=to[pre[p]^1]; //往前走
}
maxflow+=inc[t]; //最大流加上当前增广路到汇点的流量
}
int main() {
cnt=1; //重要!网络流里面的所有cnt都从1开始,来成对存储!
cin>>n>>m>>s>>t;
while(m--) {
int u,v,w;
cin>>u>>v>>w;
//直接建立残量网络
add(u,v,w);
add(v,u,0);
}
//EK算法的核心
while(bfs()) //一直找增广路
update(); //更新权值,并增加最大流
cout<<maxflow; //输出最大流
return 0;
}
为什么y总是从0开始呢 那个cnt
他的idx++是放在后面的,所以idx从0开始,我这里是从2开始,都是可以的