> 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.

• 我第一回听说任意图匹配可以这么搞成二分图的，那它还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