[ Edmonds–Karp algorithm ,Flow] 網路流Edmonds–Karp算法

這是最基本的多項式時間網路流演算法，因此在這裡我多了一些變化，首先是一般用鄰接矩陣，複雜度$\ord{\abs{V}^5}$的做法：

	#include<string.h>
	#include<limits.h>
	#include<queue>
	#include<algorithm>
	#define MAXN 100
	int n,m;/*點數、邊數*/
	int g[MAXN+5][MAXN+5],f[MAXN+5][MAXN+5],r[MAXN+5][MAXN+5];
	/*容量上限、流量、剩餘容量*/
	int v[MAXN+5];/*經過的點*/
	int pa[MAXN+5];/*紀錄路徑*/
	int d[MAXN+5];/*紀錄流量瓶頸*/
	inline int bfs(int s,int t){
	memset(v,0,sizeof(v));
	std::queue<int >q;
	q.push(s);
	v[s]=1;
	pa[s]=-1;
	d[s]=INT_MAX;
	while(q.size()){
	int x=q.front();q.pop();
	for(int i=1;i<=n;++i){
	if(v[i]||!r[x][i])continue;
	v[i]=1;
	pa[i]=x;
	d[i]=std::min(d[x],r[x][i]);
	q.push(i);
	if(i==t)return d[t];
	}
	}
	return 0;
	}
	inline int edmonds_karp(int s,int t){
	memset(f,0,sizeof(f));
	memcpy(r,g,sizeof(g));
	int ans=0,tmd;
	for(;(tmd=bfs(s,t));ans+=tmd){
	for(int i=t;~pa[i];i=pa[i]){
	f[pa[i]][i]+=tmd;
	f[i][pa[i]]-=tmd;
	r[i][pa[i]]=g[i][pa[i]]-f[i][pa[i]];
	r[pa[i]][i]=g[pa[i]][i]-f[pa[i]][i];
	}
	}
	return ans;
	}

view raw Edmonds Karp.cpp hosted with ❤ by GitHub

接著是使用鄰接串列，複雜度是$\ord{\abs{E}^2\abs{V}}$的作法：

	#include<cstring>
	#include<climits>
	#include<queue>
	#include<algorithm>
	template<typename T>
	struct Edmonds_Karp{
	static const int MAXN=105;
	static const T INF=INT_MAX;
	struct edge{
	int v,pre;
	T cap,r;
	edge(int v,int pre,T cap):v(v),pre(pre),cap(cap),r(cap){}
	};
	int g[MAXN],n;
	bool vis[MAXN];
	int pa[MAXN];
	T d[MAXN];
	std::vector<edge> e;
	void init(int _n){
	memset(g,-1,sizeof(int)*((n=_n)+1));
	e.clear();
	}
	void add_edge(int u,int v,T cap,bool directed=false){
	e.push_back(edge(v,g[u],cap));
	g[u]=e.size()-1;
	e.push_back(edge(u,g[v],directed?0:cap));
	g[v]=e.size()-1;
	}
	T bfs(int s,int t){
	memset(vis,0,sizeof(bool)*(n+1));
	std::queue<int> q;
	q.push(s);
	vis[s]=1;
	pa[s]=-1;
	d[s]=INF;
	while(q.size()){
	int u=q.front();q.pop();
	for(int i=g[u];~i;i=e[i].pre){
	if(vis[e[i].v]||e[i].r==0)continue;
	vis[e[i].v]=1;
	pa[e[i].v]=i;
	d[e[i].v]=std::min(d[u],e[i].r);
	q.push(e[i].v);
	if(e[i].v==t)return d[t];
	}
	}
	return 0;
	}
	T edmonds_karp(int s,int t){
	T ans=0,tmd;
	for(;(tmd=bfs(s,t));ans+=tmd){
	for(int u=t;~pa[u];){
	int i=pa[u];
	e[i].r-=tmd;
	e[i^1].r+=tmd;
	u=e[i^1].v;
	}
	}
	return ans;
	}
	};

view raw Edmonds Karp3.cpp hosted with ❤ by GitHub

最近幫學長寫作業的時候，又發現了一個不需要多紀錄反邊的做法，但是每個點要同時記錄入邊和出邊，這樣可以用較少的記憶體完成演算法：

	#include<cstring>
	#include<climits>
	#include<queue>
	#include<algorithm>
	template<typename T>
	struct Edmonds_Karp{
	static const int MAXN=105;
	static const T INF=INT_MAX;
	struct Edge{
	int u,v;
	T cap,r;
	Edge(int u,int v,const T &cap):u(u),v(v),cap(cap),r(cap){}
	};
	std::vector<Edge> edge;
	std::vector<int> in[MAXN];
	std::vector<int> out[MAXN];
	bool vis[MAXN];
	int pa[MAXN];
	T d[MAXN];
	int n;
	void init(int _n){
	edge.clear();
	for(n=_n++;_n--;){
	in[_n].clear();
	out[_n].clear();
	}
	}
	void add_edge(int u,int v,const T &cap){
	in[u].emplace_back(edge.size());
	out[v].emplace_back(edge.size());
	edge.emplace_back(u,v,cap);
	}
	T bfs(int s,int t){
	memset(vis,0,sizeof(bool)*(n+1));
	std::queue<int> q;
	q.push(s);
	vis[s]=1;
	pa[s]=-1;
	d[s]=INF;
	while(q.size()){
	int u=q.front();q.pop();
	for(auto i:in[u]){
	const auto &e=edge[i];
	if(vis[e.v]||e.r==0)continue;
	vis[e.v]=1;
	pa[e.v]=i;
	d[e.v]=std::min(d[u],e.r);
	q.push(e.v);
	if(e.v==t)return d[t];
	}
	for(auto i:out[u]){
	const auto &e=edge[i];
	if(vis[e.u]||e.r==e.cap)continue;
	vis[e.u]=1;
	pa[e.u]=i;
	d[e.u]=std::min(d[u],e.cap-e.r);
	q.push(e.u);
	if(e.u==t)return d[t];
	}
	}
	return 0;
	}
	T edmonds_karp(int s,int t){
	T ans=0,tmd;
	for(;(tmd=bfs(s,t));ans+=tmd){
	for(int u=t;~pa[u];){
	auto &e=edge[pa[u]];
	if(e.v==u){
	e.r-=tmd;
	u=e.u;
	}else{
	e.r+=tmd;
	u=e.v;
	}
	}
	}
	return ans;
	}
	};

view raw Edmonds Karp2.cpp hosted with ❤ by GitHub