[ Improved Shortest Augmenting Paths,ISAP ,Flow ] 網路流ISAP算法

使用gap優化(間隙優化)
使用當前弧優化

這裡提供遞迴與非遞迴兩種實現
基本上兩個版本效能差不多
遞迴版本:

	#include<string.h>
	#include<limits.h>
	#include<vector>
	#include<algorithm>
	template<typename T>
	struct ISAP{
	static const int MAXN=105;
	static const T INF=INT_MAX;
	int n;//點數
	int d[MAXN],gap[MAXN],cur[MAXN];
	//層次、gap[i]=層次為i的點之個數、當前弧優化
	struct edge{
	int v,pre;
	T cap,flow,r;
	edge(int v,int pre,T cap):v(v),pre(pre),cap(cap),flow(0),r(cap){}
	};
	int g[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 dfs(int u,int s,int t,T cur_flow=INF){
	if(u==t)return cur_flow;
	T tf=cur_flow,df;
	for(int &i=cur[u];~i;i=e[i].pre){
	if(e[i].r&&d[u]==d[e[i].v]+1){
	df=dfs(e[i].v,s,t,std::min(tf,e[i].r));
	e[i].flow+=df;
	e[i^1].flow-=df;
	e[i].r-=df;
	e[i^1].r+=df;
	if(!(tf-=df)||d[s]==n)return cur_flow-tf;
	}
	}
	int minh=n;
	for(int i=cur[u]=g[u];~i;i=e[i].pre){
	if(e[i].r&&d[e[i].v]<minh)minh=d[e[i].v];
	}
	if(!--gap[d[u]])d[s]=n;
	else ++gap[d[u]=++minh];
	return cur_flow-tf;
	}
	T isap(int s,int t,bool clean=true){
	memset(d,0,sizeof(int)*(n+1));
	memset(gap,0,sizeof(int)*(n+1));
	memcpy(cur,g,sizeof(int)*(n+1));
	if(clean){
	for(size_t i=0;i<e.size();++i){
	e[i].flow=0;
	e[i].r=e[i].cap;
	}
	}
	T max_flow=0;
	for(gap[0]=n;d[s]<n;)max_flow+=dfs(s,s,t);
	return max_flow;
	}
	std::vector<int> cut_e;//最小割邊集
	bool vis[MAXN];
	void dfs_cut(int u){
	vis[u]=1;//表示u屬於source的最小割集
	for(int i=g[u];~i;i=e[i].pre){
	if(e[i].flow<e[i].cap&&!vis[e[i].v])dfs_cut(e[i].v);
	}
	}
	T min_cut(int s,int t){
	T ans=isap(s,t);
	memset(vis,0,sizeof(bool)*(n+1));
	dfs_cut(s),cut_e.clear();
	for(int u=0;u<=n;++u){
	if(vis[u])for(int i=g[u];~i;i=e[i].pre){
	if(!vis[e[i].v])cut_e.push_back(i);
	}
	}
	return ans;
	}
	};

view raw isap_dfs.cpp hosted with ❤ by GitHub

非遞迴版本:

	#include<string.h>
	#include<limits.h>
	#include<vector>
	#include<algorithm>
	template<typename T>
	struct ISAP{
	static const int MAXN=105;
	static const T INF=INT_MAX;
	int n;//點數
	int d[MAXN],gap[MAXN],pre[MAXN],cur[MAXN];
	//層次、gap[i]=層次為i的點之個數、前一個節點、當前弧優化
	struct edge{
	int v,pre;
	T cap,flow,r;
	edge(int v,int pre,T cap):v(v),pre(pre),cap(cap),flow(0),r(cap){}
	};
	int g[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 isap(int s,int t,bool clean=true){
	T cur_flow,max_flow=0;
	int u=s;
	memset(d,0,sizeof(int)*(n+1));
	memset(gap,0,sizeof(int)*(n+1));
	memcpy(cur,g,sizeof(int)*(n+1));
	if(clean){
	for(size_t i=0;i<e.size();++i){
	e[i].flow=0;
	e[i].r=e[i].cap;
	}
	}
	for(gap[0]=n;d[s]<n;){
	if(u==t){
	cur_flow=INF;
	for(int i=s;i!=t;i=e[cur[i]].v){
	if(cur_flow>e[cur[i]].r)cur_flow=e[cur[i]].r;
	}
	for(int i=s;i!=t;i=e[cur[i]].v){
	e[cur[i]].flow+=cur_flow;
	e[cur[i]^1].flow-=cur_flow;
	e[cur[i]].r-=cur_flow;
	e[cur[i]^1].r+=cur_flow;
	}
	max_flow+=cur_flow;
	u=s;
	}
	int i;
	for(i=cur[u];~i;i=e[i].pre){
	if(e[i].r&&d[u]==d[e[i].v]+1)break;
	}
	if(~i){
	cur[u]=i;
	pre[e[i].v]=u;
	u=e[i].v;
	}else{
	if(!--gap[d[u]])break;
	for(d[u]=n,i=cur[u]=g[u];~i;i=e[i].pre){
	if(e[i].r&&d[e[i].v]<d[u])d[u]=d[e[i].v];
	}
	++gap[++d[u]];
	if(u!=s)u=pre[u];
	}
	}
	return max_flow;
	}
	std::vector<int> cut_e;//最小割邊集
	bool vis[MAXN];
	void dfs_cut(int u){
	vis[u]=1;//表示u屬於source的最小割集
	for(int i=g[u];~i;i=e[i].pre){
	if(e[i].flow<e[i].cap&&!vis[e[i].v])dfs_cut(e[i].v);
	}
	}
	T min_cut(int s,int t){
	T ans=isap(s,t);
	memset(vis,0,sizeof(bool)*(n+1));
	dfs_cut(s),cut_e.clear();
	for(int u=0;u<=n;++u){
	if(vis[u])for(int i=g[u];~i;i=e[i].pre){
	if(!vis[e[i].v])cut_e.push_back(i);
	}
	}
	return ans;
	}
	};

view raw isap.cpp hosted with ❤ by GitHub