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 frkstyc at 2005-08-03 01:39:17
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) sunmoonstar_love 2005-08-03 01:41:31
- 2404 Jogging Trails (0) frkstyc 2005-08-03 01:42:39
  - 做过这题的冒个泡，我一起床就11点多了 (0) sunmoonstar_love 2005-08-03 12:32:35

Post your reply here:

Home Page Go Back To top