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

求问此题KM算法的解法……

Posted by Ruby931031 at 2013-05-20 00:38:48 on Problem 3308 and last updated at 2013-05-20 00:40:52
或者没办法用KM算法解?

虽然最小点权覆盖 和 最大边权匹配是对偶问题,但是KM算法中求解的最大权匹配是不断修正顶标的,
也就是说最终虽然求出来了一个最小点权覆盖&&最大权匹配,不过事先却不能知道到底是哪一组顶标下的最小点权覆盖(事实上很可能不是原图中给出的点权)

感觉就像Stoer-Wagner算法求无向图的全局最小割一样,每一次循环都求出了一个s-t最小割,但是在求之前却不知道这一次求出的s-t最小割中的s和t到底是哪两个点。
如果先前给定好两个点x和y,是不能用这个算法来求出x-y最小割的。

不知道我理解的对不对?对的话我就不纠结KM算法了,直接换最大流做……

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