费用流算法
  • 板块学术版
  • 楼主IceYukino
  • 当前回复15
  • 已保存回复15
  • 发布时间2023/1/7 10:45
  • 上次更新2023/10/24 05:19:14
查看原帖
费用流算法
214538
IceYukino楼主2023/1/7 10:45

平时写的Dinic费用流复杂度是多少?有更优的费用流算法吗?

我写的Dinic:

int bfs(){
	for(int i=1;i<=n+1;i++) d[i]=INF,vis[i]=0;
	queue<int>q;q.push(S);d[S]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		cur[u]=head[u];vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int y=e[i].to;
			if(d[y]>d[u]+e[i].c&&e[i].w){
				d[y]=d[u]+e[i].c;
				if(!vis[y]){
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
	return (d[T]!=INF);
}
int dfs(int x,int flow){
	if(flow==0||x==T) return flow;
	int res=flow;vis[x]=1;
	for(int i=cur[x];i;i=e[i].nxt){
		int y=e[i].to;cur[x]=i;
		if(!vis[y]&&d[y]==d[x]+e[i].c&&e[i].w){
			int tmp=dfs(y,min(res,e[i].w));
			if(tmp==0) d[y]=-INF;
			e[i].w-=tmp;e[i^1].w+=tmp;res-=tmp;
			cost+=tmp*e[i].c;
		}
	}
	return flow-res;
}

int flow=0,maxflow=0;
while(bfs())
	while(flow=dfs(S,INF)) maxflow+=flow;
2023/1/7 10:45
加载中...