洛谷$P4126\ [AHOI2009]$最小割 图论

正解:网络流+$tarjan$

解题报告:

$umm$最小割的判定问题$QwQ$,因为并不会做是看的题解才会的,所以也没什么推导过程直接放结论趴$QwQ$

首先跑个最大流,然后有.

1)可行流($x,y$)的充要条件:满流&残余网络中不存在$x$到$y$的路径

2)必然流($x,y$)的充要条件:满流&残余网络中$ST$分别能到达$xy$

证明的话都可以用反证法?

对于1,挺显然的还,就如果存在$x$到$y$的路径,说明并没有割开,显然不属于最小割

对于2,我取一边为例,若$S$不能到达$x$,则说明一定有一条边也能被割开,则可以割开那条边,因此这条边不是必然边.$over$

然后具体体现的话就是.

1)满流&$xy$不属于一个$SCC$中

2)满流&$xy$分别与$ST$属于一个$SCC$中

所以就跑个最大流然后跑个$tarjan$就欧克!$over$

补一个易错点,,,虽然我$jio$得可能就我一个人那么傻逼被这个傻逼的易错点坑了1$h$,,,$QAQ$

就,在用当前弧优化的时候不是要在每次$dinic$中$bfs$后给所有$cur$赋值为$head$嘛,因为我之前一直是$S$是最小$T$是最大所以我就一直打的$for(S,T)$.但是在这题里应该是$for(1,n)$,,,$QAQ$

没了,$over$