关于本题为何无解时求最大流可能会死循环
查看原帖
关于本题为何无解时求最大流可能会死循环
449265
wind_whisper楼主2022/1/29 16:20

本人做这道题的时候是先求出最大流,判断如果超过 INFINF 则报告无解,结果 #19蜜汁TLE
调了很长时间不知道为什么,后来仔细看了看题解代码需要在 dinic 代码内部判断如果当前流超过了 INFINF,则直接跳出循环并判断无解。
也就是:

void dinic(){
	double flow(0),tmp(0);
	while(bfs()){
		while((tmp=dfs(s,inf))>eps) flow+=tmp;
		if(flow>=inf){
			puts("-1");return;
		}
	}
	printf("%lf\n",flow);
	return;
}

然后就 A了
不太明白为什么会死循环,求大佬解答,感谢!

2022/1/29 16:20
加载中...