关于网络流算法效率的疑问

做了一个题，用网络流来求二分图最大匹配

左右部点数量 76000，每个左部点向右连 3~4 条边。总边数 4e5 左右

我做的事：

一开始使用 ISAP，在本机跑了 2.5 秒才跑出来最大匹配。
尝试换成 Dinic，跑了 1 秒
对 Dinic 做了一点小改动（见下文代码），瞬间跑完（<0.2秒）

我的疑问：

为什么 ISAP 会这么慢。我以为 ISAP 对 Dinic 有常数优化，至少不会比 Dinic 慢，就一直写 ISAP。是我的理解有误吗？还是说 ISAP 在二分图这种特殊情况下有特殊变化？
为什么我对 Dinic 的那一小行修改（下文）能使得代码跑的非常快？我以为我的那行代码是优化
是我的模板出现了问题吗 /kel

这三份代码的正确性应该是都没问题的（从我的提交来看），只是耗时的问题？

下面是上述三份代码的网络流部分（其他部分完全相同）

ISAP

CPP

template<int N,int M,class D,D INF>
class ISAP{
	struct edge{
		int v;
		int nxt;
		D w;
	}e[M*2+5];
	int ecnt=1;
	int head[N+5],cur[N+5],dep[N+5],gap[N+5];
	int n,s,t;

	void add_e(int u,int v,D w){
		e[++ecnt]={v,head[u],w};
		head[u]=ecnt;
	}

	void bfs(){
		static queue<int> q;
		while(!q.empty())	q.pop();
		foru(i,1,n)	dep[i]=-1,gap[i]=0;
		dep[t]=0,gap[0]=1;
		q.push(t);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=head[u];i;i=e[i].nxt){
				int v=e[i].v;
				if(dep[v]!=-1)	continue;
				dep[v]=dep[u]+1;
				gap[dep[v]]++;
				q.push(v);
			}
		}
	}
	D dfs(int u,D flow){
		if(u==t)	return flow;
		D used=0;
		for(int &i=cur[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(e[i].w==0 || dep[u]!=dep[v]+1)	continue;
			D x=dfs(v,min(flow-used,e[i].w));
			e[i].w-=x;
			e[i^1].w+=x;
			used+=x;
			if(used==flow)	return used;
		}
		gap[dep[u]]--;
		if(gap[dep[u]]==0)	dep[s]=n+1;
		dep[u]++;
		gap[dep[u]]++;
		return used;
	}
public:
	void set(int _n,int _s,int _t){
		n=_n,s=_s,t=_t;
	}
	int add_edge(int u,int v,D w){
		add_e(u,v,w);
		add_e(v,u,0);
		return ecnt-1;
	}
	D maxflow(){
		bfs();
		D flow=0;
		while(dep[s]<n){
			foru(i,1,n)	cur[i]=head[i];
			flow+=dfs(s,INF);
		}
		return flow;
	}
};

Dinic（跑了一秒的）

CPP

template<int N,int M,class D,D INF>
class Dinic{
	struct edge{
		int v;
		int nxt;
		D w;
	}e[M*2+5];
	int ecnt=1;
	int head[N+5],cur[N+5],dep[N+5],gap[N+5];
	int n,s,t;

	void add_e(int u,int v,D w){
		e[++ecnt]={v,head[u],w};
		head[u]=ecnt;
	}

	bool bfs(){
		static queue<int> q;
		memset(dep,-1,sizeof dep);
		memcpy(cur,head,sizeof head);
		dep[s]=0;
		q.push(s);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=head[u];i;i=e[i].nxt){
				int v=e[i].v;
				if(dep[v]!=-1 || e[i].w==0)	continue;
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
		return (dep[t]!=-1);
	}
	D dfs(int u,D flow){
		if(u==t)	return flow;
		D used=0;
		for(int &i=cur[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(e[i].w==0 || dep[u]!=dep[v]-1)	continue;
			D x=dfs(v,min(flow-used,e[i].w));
			e[i].w-=x;
			e[i^1].w+=x;
			used+=x;
			if(used==flow)	return used;
		}
		return used;
	}
public:
	void set(int _n,int _s,int _t){
		n=_n,s=_s,t=_t;
	}
	int add_edge(int u,int v,D w){
		add_e(u,v,w);
		add_e(v,u,0);
		return ecnt-1;
	}
	D maxflow(){
		D flow=0;
		while(bfs()){
			flow+=dfs(s,INF);
			// cerr<<flow<<endl;
		}
		return flow;
	}
};

Dinic（瞬间跑完的）

事实上只改了 dfs 函数内的一行

CPP

D dfs(int u,D flow){
  if(u==t)	return flow;
  D used=0;
  for(int &i=cur[u];i;i=e[i].nxt){
    int v=e[i].v;
    if(e[i].w==0 || dep[u]!=dep[v]-1)	continue;
    D x=dfs(v,min(flow-used,e[i].w));
    e[i].w-=x;
    e[i^1].w+=x;
    used+=x;
    // if(used==flow)	return used;
    // 注释了掉这行就瞬间跑完了。提交后总体用时快了 30%
  }
  return used;
}

关于网络流算法效率的疑问

讨论操作

回复

相关推荐

关于网络流算法效率的疑问