存在一个最优匹配M将2n个奇数度的点分成两部分n1,n2，

那么其逆匹配M'也可将2n个奇数度的点分成两部分n2,n1；

那么将这两个匹配M与M'合在一起新的匹配P，那么就是分成n1+n2,n2+n1两部分

这个P也就一定是我直接用 maximum-weight matching  得到的结果了，

因为最优加最优（在这个问题中）还是最优的

• 首先的问题是你不能保证匹配的结果是对称的 (202) frkstyc 2005-08-03 01:39:17
  • 我理论功底不够，证明不了，有个题来实践一下就好了 (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
• 直觉是：只有对称才可能成为最优而被我的程序找到， (202) sunmoonstar_love 2005-08-03 01:44:29
  • 写一个看看吧 (0) frkstyc 2005-08-03 01:44:43
    • 明天吧，先睡觉了 (0) sunmoonstar_love 2005-08-03 01:46:13