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

想明白了

Posted by Ruby931031 at 2013-05-21 14:29:41 on Problem 3686
In Reply To:KM算法在左右两边点数不相等的时候到底应该怎么办？个人觉得网上大多数解题报告有问题 Posted by:Ruby931031 at 2013-05-20 14:29:23 
左右两边点数不等时，KM算法的正确性也是可以得到保证的。原因如下：
由KM算法中可行点标的定义，有：
任意匹配的权值 <= 该匹配所覆盖的所有点的顶标值 <= KM算法所得到的匹配所覆盖的所有点的顶标值 = KM算法所得到的的匹配的权值

上面的证明与网上大多数证明不同点在于，网上的证明中只是模糊地说“图中所有点的顶标值”，这只在两点集点数相等时才正确。

上面第二个不等号最为关键，它的理由是：假定|X|<=|Y|，则任意时刻，Y集合中KM算法所取的匹配未覆盖的点的顶标必为0！
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