| ||||||||||
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 |
本题就是要找最小点覆盖,根据König 定理就是求最大二分匹配了In Reply To:为什么要用二分图匹配啊?? Posted by:killua_hzl at 2008-08-05 14:36:46 本题就是要找最小点覆盖,根据König 定理就是求最大二分匹配了 König 定理是一个二分图中很重要的定理---一个二分图中的最大匹配数等于这个图中的最小点覆盖数。最小点覆盖:假如选了一个点就相当于覆盖了以它为端点的所有边,你需要选择最少的点来覆盖所有的边。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator