Construct a graph G’ = (X’, E’) whose vertex set consists of all odd-degree vertices in G and whose edge set contains an edge joining each pair of vertices. Let the weight of each edge equal a very large number minus the length of a shortest path between the corresponding two vertices in graph G as found by the Floyd algorithm.
Next, the postman should find a maximum-weight matching for graph G’ using the maximum-weight matching algorithm.

• 那打算怎么匹配？ (450) frkstyc 2005-08-03 01:15:53
• 一起匹配然后除2，为什么不行?我看很多匹配都是这么做的 (450) sunmoonstar_love 2005-08-03 01:20:57
  • 我第一回听说任意图匹配可以这么搞成二分图的，那它还NP干什么…… (0) frkstyc 2005-08-03 01:22:06
    • Re:任意图匹配是np的么？ (0) PojMj 2006-08-08 17:13:36
      • 你要是主ID，我把PojMj这个ID吃了 (0) sunmoonstar_love 2006-08-08 19:50:08
  • 里面看 (182) sunmoonstar_love 2005-08-03 01:37:25
    • 首先的问题是你不能保证匹配的结果是对称的 (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