Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

只用跑一次最大流+一次floyd的解法

Posted by hassenio at 2012-01-28 14:20:14 on Problem 1815 and last updated at 2012-01-28 14:21:30
算法是这样的:首先按照常规方法拆点建图,跑一次最大流,得到残留网络。
规定如果在残留网络中从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

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator