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 lvcheng at 2010-04-11 12:21:21 on Problem 3020
In Reply To:AC了 不解 为什么是 *的总数-最大匹配数/2 呢?大牛指点 Posted by:GaryLiang at 2009-09-13 22:24:53
因为此题要求选出最少的边数,使得每个点都被覆盖大到,而这正是最小路径覆盖。
根据定理,最小路径覆盖=点数V-最大独立集。对于二分图,最大独立集=最大匹配。
所以Ans=(V-最大匹配),但注意到此时的V=*个数×2。   而对于两个点(i,j) (i<j).
不论在二分图中有边相连还是无边相连,求出的Ans是原来的两倍,即求出的最大匹配中对于(i,j)和(j,i)两对点都进行了匹配,而我们只需要进行选其中一个即可。所以Ans需要除以2,也就是:  *个数 - 最大匹配/2。
个人想法。呵呵。

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