标签为 [Tarjan] 的文章

BZOJ1797 mincut最小割

题目大意 给定一张网络,询问其中的每条有向边是否可能属于某一个最小割,是否一定属于所有最小割。 Solution 题目是最小割,肯定先跑一次网络流模板…… 求出最小割后,就可以得到一个残余网络。如果对这个残余网络进行强联通缩点,可以发现s,t一定不在同一个强联通分量中。否则,s,t之间肯定还能继续增流,求出的肯定不是最大流。 如果原图中一条边是u->v的,且任意一点u缩点后属于belong[u]的强联通分量中。 如果这条边没有满流,显然它不可能属于某一个最小割。 如果belong[u]!=belong[v],则边u->v可以属于某一个最小割。 ......