对于网络流算法中Dinic与ISAP的效率比较

luogu 模板题 P3376 网络最大流

作者自测，可能因为代码习惯等原因常数不同，个人的整理

对此题，目前使用两种算法，均 A C AC AC

D i n i c Dinic Dinic 970 m s 970ms 970ms
D i n i c Dinic Dinic + 当前弧 762 m s 762ms 762ms
D i n i c Dinic Dinic + 当前弧 + 多路增广 162 m s 162ms 162ms
I S A P ISAP ISAP + g a p gap gap优化 + 多路增广 83 m s 83ms 83ms
I S A P ISAP ISAP + g a p gap gap优化 + 当前弧 + 多路增广 72 m s 72ms 72ms

效率相差太大了！！！

（前几个 D i n i c Dinic Dinic很久以前写的,常数方面可能也有一些原因）

以下为代码（因为是模板题，均带注释）

1. D i n i c Dinic Dinic 970 m s 970ms 970ms

#include<iostream>	//Dinic
#include<cstdio>
#include<cstring>
#include<queue>
#define re register
using namespace std;

inline int read(){
	int s=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';ch=getchar();
	}
	return s*f;
}

const int N=10000+5,M=100000*2+5,inf=0xfffffff;
int n,m,s,t;
struct E{
	int next,to,w;
	// w 每一条边的残量 
}e[M];
int head[N],cnt=-1; //cnt初值为-1，反边直接 ^ 
inline void add_edge(int u,int v,int w){
	e[++cnt].next=head[u],e[cnt].to=v,e[cnt].w=w,head[u]=cnt;
	return;
}
int dep[N];	//深度 
queue<int> q;
bool bfs(){	//分层图 
//保证不会有深度低的流向深度高的边，也不会用同层的边流 
	while(!q.empty()) q.pop();
	memset(dep,0,sizeof(dep));
	dep[s]=1;	//源点深度为1
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(re int i=head[u];i!=-1;i=e[i].next){ //i!=-1
			int v=e[i].to;
			if(e[i].w>0 && dep[v]==0){
			//若该残量不为0，且V[i]还未分配深度，则给其分配深度并放入队列
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	if(dep[t]==0) return 0; //当汇点的深度不存在时，说明不存在分层图，同时也说明不存在增广路
	return 1;
}
int dfs(int u,int dist){ //u是当前节点，dist是当前流量 
	if(u==t) return dist;	//到达汇点 
	for(re int i=head[u];i!=-1;i=e[i].next){
		int v=e[i].to;
		if(dep[v]==dep[u]+1 && e[i].w!=0){
		//分层图和残量不为0两个条件	
			int d=dfs(v,min(dist,e[i].w)); //向下增广 
			if(d>0){	//若增广成功 
				e[i].w-=d;		正向边减 
				e[i^1].w+=d;	//反向边加 
				return d;		//向上传递 
			}
		}
	}
	return 0;	//否则说明没有增广路，返回0
}
int Dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	return ans;
}

int main(){
	//freopen("testdata.in","r",stdin);
	memset(head,-1,sizeof(head));
	n=read(),m=read(),s=read(),t=read();
	for(re int i=1,x,y,z;i<=m;i++){
		x=read(),y=read(),z=read();
		add_edge(x,y,z);
		add_edge(y,x,0);	//建反向边 
	//当我们在寻找增广路的时候，在前面找出的不一定是最优解 
	//建反向边有反悔的机会  
	}
	printf("%d\n",Dinic());
	return 0;
}
/*
以上是未加任何优化的Dinic  
*/

2. D i n i c Dinic Dinic + 当前弧 762 m s 762ms 762ms

#include<iostream>	//Dinic + 当前弧优化 
#include<cstdio>
#include<cstring>
#include<queue>
#define re register
using namespace std;

inline int read(){
	int s=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}

const int N=10000+5,M=100000*2+5,inf=0xfffffff;
int n,m,s,t;
struct E{
	int next,to,w;
}e[M];
int head[N],cnt=-1;
inline void add_edge(int u,int v,int w){
	e[++cnt].next=head[u],e[cnt].to=v,e[cnt].w=w,head[u]=cnt;
	return;
}
int dep[N];
int cur[N]; //cur就是记录当前点u循环到了哪一条边  
queue<int> q;
bool bfs(){
	while(!q.empty()) q.pop();
	memset(dep,0,sizeof(dep));
	dep[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(re int i=head[u];i!=-1;i=e[i].next){
			int v=e[i].to;
			if(e[i].w>0 && dep[v]==0){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	if(dep[t]==0) return 0;
	return 1;
}
int dfs(int u,int dist){
	if(u==t) return dist;
	for(re int &i=cur[u];i!=-1;i=e[i].next){
//注意这里的&符号，这样i增加的同时也能改变cur[u]的值，达到记录当前弧的目的 
		int v=e[i].to;
		if(dep[v]==dep[u]+1 && e[i].w!=0){
			int d=dfs(v,min(dist,e[i].w));
			if(d>0){
				e[i].w-=d;	
				e[i^1].w+=d;
				return d;
			}
		}
	}
	return 0;
}
int Dinic(){
	int ans=0;
	while(bfs()){
		for(re int i=1;i<=n;i++) cur[i]=head[i];
	//每一次建立完分层图后都要把cur置为每一个点的第一条边
		ans+=dfs(s,inf);
	}
	return ans;
}

int main(){
//	freopen("testdata.in","r",stdin);
	memset(head,-1,sizeof(head));
	n=read(),m=read(),s=read(),t=read();
	for(re int i=1,x,y,z;i<=m;i++){
		x=read(),y=read(),z=read();
		add_edge(x,y,z);
		add_edge(y,x,0);
	}
	printf("%d\n",Dinic());
	return 0;
}

3. D i n i c Dinic Dinic + 当前弧 + 多路增广 162 m s 162ms 162ms

#include<iostream>	//Dinic + 多路增广 + 当前弧优化 
#include<cstdio>
#include<cstring>
#include<queue>
#define re register
using namespace std;

inline int read(){
	int s=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}

const int N=10000+5,M=100000+5,inf=0xfffffff;
int n,m,s,t,maxflow;
struct E{
	int next,to,w;
}e[M<<1];
int head[N],cnt=-1;
inline void add_edge(int u,int v,int w){
	e[++cnt].next=head[u],e[cnt].to=v,e[cnt].w=w,head[u]=cnt;
	return;
}

int dep[N];
int cur[N]; //cur就是记录当前点u循环到了哪一条边  2. 
queue<int> q;
inline bool bfs(){
	while(!q.empty()) q.pop();
	memset(dep,0,sizeof(dep));
	dep[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(re int i=head[u];~i;i=e[i].next){
			int v=e[i].to;
			if(e[i].w>0 && dep[v]==0){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	if(dep[t]==0) return 0;
	return 1;
}
int dfs(int u,int flow){	//寻找增广路 flow是当前增广路上最小边权   
	if(u==t){
		maxflow+=flow;	//直接累加答案  
		return flow;
	}
	int used=0; //表示这个点的流量用了多少  
	//这个实际上是直接在dfs时实现多路增广  1. 
	for(re int &i=cur[u];~i;i=e[i].next){
//注意这里的&符号，这样i增加的同时也能改变cur[u]的值，达到记录当前弧的目的 2. 
		int v=e[i].to;
		if(dep[v]==dep[u]+1 && e[i].w!=0){
			int d=dfs(v,min(flow-used,e[i].w));
			if(d>0){ 
				e[i].w-=d;	
				e[i^1].w+=d;
				used+=d;
				if(used==flow) break; //该点流量满了,没必要继续找了 1. 
				//在dfs时找到一条增广路不直接返回,而是修改used的值 
				//如果used未达到流量上限flow,可以继续找其他增广路     
			}
		}
	}
	return used; //返回该点已使用流量  1. 
}
int Dinic(){
	while(bfs()){
		for(re int i=1;i<=n;i++) cur[i]=head[i];
	//每一次建立完分层图后都要把cur置为每一个点的第一条边 
		dfs(s,inf);	//记得初始流量设为inf s 
	}
	return maxflow;
}

int main(){
	memset(head,-1,sizeof(head));
	n=read(),m=read(),s=read(),t=read();
	for(re int i=1,x,y,z;i<=m;i++){
		x=read(),y=read(),z=read();
		add_edge(x,y,z);
		add_edge(y,x,0);
	}
	printf("%d\n",Dinic());
	return 0;
}
/*
这段代码使用了两个优化 
1.dfs时多路增广 
2.当前弧优化 
(当时为了当前弧优化翻了好多好多博客都是莫名其妙看到一个used, 
完全看不懂,头都要晕掉 
还好现在看到了一篇博客(之前没仔细看),真的写得好好啊,清晰易懂) 

https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-jiang-xie-zhi-dinic 
Dinic  
*/

优秀的讲解 D i n i c Dinic Dinic

4. I S A P ISAP ISAP + g a p gap gap优化 + 多路增广 83 m s 83ms 83ms

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define re register
#define il inline
#define ll long long
using namespace std;

il int read(){
    int s=0,f=0;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-'),c=getchar();
    while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
    return f?-s:s;
}

const int N=1e4+5,M=1e5+5,inf=0x3f3f3f3f;
int n,m,s,t,maxflow;
struct E{
	int next,to,w;
}e[M<<1];	//双向边!  
int head[N],cnt;
il void add_edge(int u,int v,int w){
	e[cnt].next=head[u],e[cnt].to=v,e[cnt].w=w,head[u]=cnt++;
}

int dep[N],gap[N];
//gap[i]表示深度为i的点的数量 优化 
queue<int> q;
il void bfs(){
	memset(dep,-1,sizeof(dep));
	memset(gap,0,sizeof(gap));
	
	q.push(t),dep[t]=0,gap[0]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(re int i=head[u];~i;i=e[i].next){
			int v=e[i].to;
			if(dep[v]!=-1) continue; //防止重复改某个点 
			q.push(v);
			dep[v]=dep[u]+1,gap[dep[v]]++;
		}
	}
} 
//ISAP里的bfs对 边权!=0 这一条件并没有限制,只要在后面的dfs里判断边权就好了 

int dfs(int u,int flow){
	if(u==t){
		maxflow+=flow;
		return flow;
	}
	int used=0;
	for(re int i=head[u];~i;i=e[i].next){
		int v=e[i].to;
		if(e[i].w&&dep[v]+1==dep[u]){ //这里是dep[v]+1==dep[u] Dinic是从源点bfs的   
			int d=dfs(v,min(flow-used,e[i].w));
			if(d>0){
				e[i].w-=d;
				e[i^1].w+=d;
				used+=d;
			}
			if(used==flow) return used;
		}
	}
	//前半段和Dinic一模一样 
    //如果已经到了这里,说明该点出去的所有点都已经流过了 
    //并且从前面点传过来的流量还有剩余 
    //则此时,要对该点更改dep 
    //使得该点与该点出去的点分隔开 
    --gap[dep[u]];
    if(!gap[dep[u]]) dep[s]=n+1;
// gap优化 
//出现断层,无法到达t 
//因为我们是按照深度来往前走的,路径上的点的深度一定是连续的, 
//而t的深度为0,如果某个深度的点不存在,那么我们就无法到达t了 
    dep[u]++;	//更改dep  
    gap[dep[u]]++;
    return used;
}

il void ISAP(int s,int t){
	bfs();	//1.从t到s跑一遍bfs,标记初始深度 
	while(dep[s]<n) dfs(s,inf); //inf 
	//终止条件 dep[s]<n 
	//每走一次增广路,s层数+1,若一直没有断层,最多跑n-dep(刚dfs完时s的深度)条增广路(一共n个点) 
}

int main(){
	memset(head,-1,sizeof(head));
	n=read(),m=read(),s=read(),t=read();
	for(re int i=1,u,v,w;i<=m;++i)
		u=read(),v=read(),w=read(),
		add_edge(u,v,w),add_edge(v,u,0);
		
	ISAP(s,t);
	printf("%d\n",maxflow);
    return 0;
}

5. I S A P ISAP ISAP + g a p gap gap优化 + 当前弧 + 多路增广 72 m s 72ms 72ms

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define re register
#define il inline
#define ll long long
using namespace std;

il int read(){
    int s=0,f=0;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-'),c=getchar();
    while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
    return f?-s:s;
}

const int N=1e4+5,M=1e5+5,inf=0x3f3f3f3f;
int n,m,s,t,maxflow;
struct E{
	int next,to,w;
}e[M<<1];	//双向边!  
int head[N],cnt;
il void add_edge(int u,int v,int w){
	e[cnt].next=head[u],e[cnt].to=v,e[cnt].w=w,head[u]=cnt++;
}

int dep[N],gap[N],cur[N];
//gap[i]表示深度为i的点的数量 优化 	1. 
//cur 当前弧优化 					2. 
queue<int> q;
il void bfs(){
	memset(dep,-1,sizeof(dep));
	memset(gap,0,sizeof(gap));
	
	q.push(t),dep[t]=0,gap[0]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(re int i=head[u];~i;i=e[i].next){
			int v=e[i].to;
			if(dep[v]!=-1) continue; //防止重复改某个点 
			q.push(v);
			dep[v]=dep[u]+1,gap[dep[v]]++;
		}
	}
} 
//ISAP里的bfs对 边权!=0 这一条件并没有限制,只要在后面的dfs里判断边权就好了 

int dfs(int u,int flow){
	if(u==t){
		maxflow+=flow;
		return flow;
	}
	int used=0;
	for(re int &i=cur[u];~i;i=e[i].next){
		int v=e[i].to;
		if(e[i].w&&dep[v]+1==dep[u]){ //这里是dep[v]+1==dep[u] Dinic是从源点bfs的   
			int d=dfs(v,min(flow-used,e[i].w));
			if(d>0){
				e[i].w-=d;
				e[i^1].w+=d;
				used+=d;
			}
			if(used==flow) return used;
		}
	}
	//前半段和Dinic一模一样 
    //如果已经到了这里,说明该点出去的所有点都已经流过了 
    //并且从前面点传过来的流量还有剩余 
    //则此时,要对该点更改dep 
    //使得该点与该点出去的点分隔开 
    --gap[dep[u]];
    if(!gap[dep[u]]) dep[s]=n+1;
// gap优化 
//出现断层,无法到达t 
//因为我们是按照深度来往前走的,路径上的点的深度一定是连续的, 
//而t的深度为0,如果某个深度的点不存在,那么我们就无法到达t了 
    dep[u]++;	//更改dep  
    gap[dep[u]]++;
    return used;
}

il void ISAP(int s,int t){
	bfs();	//从t到s跑一遍bfs,标记初始深度 
	while(dep[s]<n) memcpy(cur,head,sizeof(head)),dfs(s,inf); //inf 
	//终止条件 dep[s]<n 
	//每走一次增广路,s层数+1,若一直没有断层,最多跑n-dep(刚dfs完时s的深度)条增广路(一共n个点) 
}

int main(){
	memset(head,-1,sizeof(head));
	n=read(),m=read(),s=read(),t=read();
	for(re int i=1,u,v,w;i<=m;++i)
		u=read(),v=read(),w=read(),
		add_edge(u,v,w),add_edge(v,u,0);
		
	ISAP(s,t);
	printf("%d\n",maxflow);
    return 0;
}
/*
ISAP的复杂度上界其实就是Dinic复杂度去掉bfs的部分 

最短路的修改具有连续性,即我们不需要每次求后继的标号最小值,而是直接给标号加一 

https://www.luogu.org/blog/ONE-PIECE/jiu-ji-di-zui-tai-liu-suan-fa-isap-yu-hlpp 
ISAP & HLPP

代码中使用的优化 
1.gap判断层优化 
2.当前弧优化 
3.多路增广 
*/

优秀的讲解 I S A P ISAP ISAP & H L P P HLPP HLPP

仅做一比较和整理

对于网络流算法中Dinic与ISAP的效率比较

继续阅读

POJ 2987 Firing(最大权闭合图)

POJ 2987 最大权闭合子图

poj 2987 Firing (最大流、最大权闭合图)

POJ 2987 Firing (最大权闭合图，最小割)

POJ2987_Firing_最大权闭合图

poj 2516 Minimum Cost

Poj 1511- Invitation Cards(Spfa+邻接表)

日记（周六&&差分约束）

#1394 : 网络流四·最小路径覆盖

bzoj 3681: Arietta

Android 乱码

POJ - 3436 ACM Computer Factory(最大流，拆点)

最大流模板（Dinic算法）

HDU5294 Tricks Device（最大流+SPFA） 2015 Multi-University Training Contest 1Tricks Device

POJ 3680

uva Monkeys in the Emei Mountain(区间模型)