Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
因为此题要求~~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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator