来自一个蒟蒻的问题
  • 板块学术版
  • 楼主lao_wang
  • 当前回复11
  • 已保存回复11
  • 发布时间2024/5/6 15:29
  • 上次更新2024/5/6 15:47:37
查看原帖
来自一个蒟蒻的问题
701408
lao_wang楼主2024/5/6 15:29

关于dinic求最大流不能这么写

int dfs(int u,int sum){
	if(u==t){f[u]=1;return sum ;}
	if(f[u]) return 0 ;
	f[u] = 1 ;
	int use=0 ;
	for(int i=now[u];~i;i=e[i].next){
		int x=e[i].to ;
		now[u] = i ;
		if(!e[i].w||dep[x]!=dep[u]+1) continue ;
		int temp=dfs(x,min(sum,e[i].w)) ;
		if(!temp) continue ;
		e[i].w -= temp ;
		e[i^1].w += temp ;
		use += temp ;
		f[u] = 0 ;
		if(use==sum) break ;
	}
	return use ;
}
void dinic(){
  int ans=0 ;
	while(bfs())
		ans += dfs(s,inf) ;
}

只能这么写

int dfs(int u,int sum){
	if(u==t){f[u]=1;return sum ;}
	if(f[u]) return 0 ;
	f[u] = 1 ;
	int use=0 ;
	for(int i=now[u];~i;i=e[i].next){
		int x=e[i].to ;
		now[u] = i ;
		if(!e[i].w||dep[x]!=dep[u]+1) continue ;
		int temp=dfs(x,min(sum,e[i].w)) ;
		if(!temp) continue ;
		e[i].w -= temp ;
		e[i^1].w += temp ;
		use += temp ;
		f[u] = 0 ;
		return use ;
//		if(use==sum) break ;
	}
	return use ;
}
void dinic(){
	int ans=0 ;
	while(bfs())
		do{f[t]=0,ans += dfs(s,inf) ;}while(f[t]); 
}

这件事

题目:文理分科

求大佬解惑

2024/5/6 15:29
加载中...