Detail of message

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

直觉是：只有对称才可能成为最优而被我的程序找到，

Posted by sunmoonstar_love at 2005-08-03 01:44:29
In Reply To:里面看 Posted by:sunmoonstar_love at 2005-08-03 01:37:25

> 存在一个最优匹配M将2n个奇数度的点分成两部分n1,n2，
> 
> 那么其逆匹配M'也可将2n个奇数度的点分成两部分n2,n1；
> 
> 那么将这两个匹配M与M'合在一起新的匹配P，那么就是分成n1+n2,n2+n1两部分
> 
> 这个P也就一定是我直接用 maximum-weight matching  得到的结果了，
> 
> 因为最优加最优（在这个问题中）还是最优的

Followed by:

写一个看看吧 (0) frkstyc 2005-08-03 01:44:43
- 明天吧，先睡觉了 (0) sunmoonstar_love 2005-08-03 01:46:13

Post your reply here:

Home Page Go Back To top