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 14:29:23 on Problem 3686
KM算法的要点是在相等子图中寻找完备匹配,其正确性的基石是:任何一个匹配的权值之和都不大于所有顶点的顶标之和,而能够取到相等的必然是最大权匹配。但|X|!=|Y|时,完备匹配并不需要覆盖图中所有点,因此这个证明不成立,KM算法的正确性得不到保障。


举例如下:设X1,X2的点标分别为1和2,Y1,Y2,Y3的点标分别为1,2,3,相等子图中共4条边:w<X1,Y1>=2, w<X1,Y2>=3, w<X2,Y2>=4, w<X2,Y3>=5,则可见{<X1,Y1>,<X2,Y2>}是相等子图中的一个完备匹配,但显然不是最佳匹配。

网上的很多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