本人做这道题的时候是先求出最大流,判断如果超过 INF 则报告无解,结果 #19蜜汁TLE。
调了很长时间不知道为什么,后来仔细看了看题解代码需要在 dinic
代码内部判断如果当前流超过了 INF,则直接跳出循环并判断无解。
也就是:
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了。
不太明白为什么会死循环,求大佬解答,感谢!