算法是这样的：首先按照常规方法拆点建图，跑一次最大流，得到残留网络。
规定如果在残留网络中从a到b有容量，则从a向b连条边，如此建立了一个有
2n个顶点（因为拆了点）的有向图，对有向图跑一次floyd。把所有从源点
可达的点标记为1，把所有可达汇点的点标记为2，把其他点标记为0（S-T的
割集划分，1表示这个点必须放在S里，2表示必须放在T里，0表示放两边都
可以），然后开始从小到大枚举每条边（及那n个点)。设边的起点为a终点
为b，如果a不能到达b，且a的标记不是2，且b的标记不是1，则这条边可以
作为割边（它的起点可以放在S中，终点可以放在T中），然后把所有可以
到达此边b的点（包括b本身）标记为2，把所有从a可到达的点（包括a本
身）标记为1。如此重复，直到结束。得到的割边集对应的点即为所求的。

用同样的方法可以得到有其他特殊要求的割边集或割点集。

具体的解释和一点点证明发在这儿 http://blog.sina.com.cn/s/blog_74e20d890100wv7r.html

• Re:只用跑一次最大流+一次floyd的解法 (17) Karlvin 2013-05-19 00:39:09
• Re:只用跑一次最大流+一次floyd的解法 (520) guozizheng 2017-01-04 19:29:47