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 |
如果图G满足二分图条件,则可以用二分图匹配来做.最大独立集问题: (pku1466)在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值. 如果图G满足二分图条件,则可以用二分图匹配来做.最大独立集点数 = N - 最大匹配数 我拿网页上的测试数据看下了 ,构图可以用二分图来做,且能够验证上面的公式, 但是,上面的那句话“如果图G满足二分图条件”,如果它不满足二分图呢?能有办法构出这个二分图来吗???? Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator