有没有O(MN)的算法？多谢了！

• 用匈牙利算法。。。 (20) js05 2005-05-18 17:01:18
• 永远不要用网络流做匹配，这是hqm告诉我的，匈牙利是O(N^2)的吧 (20) TN 2005-05-18 17:33:24
  • 不过够胆写的话unit capacity network的网络流可以做到O(n^0.5*m) (0) 00448264 2005-05-18 17:35:37
    • no,O(min(n^(2/3)m,m^(3/2))) (0) 00448264 2005-05-18 17:37:42
      • 算了，还是匈牙利吧，价格便宜量又足 (0) TN 2005-05-18 17:38:32
  • 谢谢诸位关注!!^_^_^_^_^正在筹划匈牙利之旅。不过用网络流做不只能是单位容量的网络流吗？ (10) c0500301036 2005-05-18 17:42:12
    • UCN的网络流比较变态，前一半用最短增广路做，后一半用Ford-Fulkerson或者Edmonds-Karp做 (14) 00448264 2005-05-18 17:44:48
      • 看样子确实比较**，还是找物美价廉的吧。哎，囊中羞涩啊 (10) c0500301036 2005-05-18 17:54:53
    • Re:谢谢诸位关注!!^_^_^_^_^正在筹划匈牙利之旅。不过用网络流做不只能是单位容量的网络流吗？ (14) liangxi11 2012-01-14 10:39:41
  • 匈牙利也是nm的吧，优化以后可以到n^0.5m，好象。。。 (0) js05 2005-05-18 20:39:14
  • ft,不会写匈牙利,写preflow用g++挤过去了 (0) ArXoR 2005-05-19 13:32:50
    • preflow又慢又麻烦，还是匈牙利好...... (2) TN 2005-05-19 13:37:21
      • preflow好写嘛,比较短...只是我不懂匈牙利,正打算开始看-_-b...菜啊~~ (4) ArXoR 2005-05-19 13:46:04
        • 匈牙利比preflow好写不少吧？ (0) TN 2005-05-19 14:08:17
          • 我找不到Hungarian Method……CLRS上也没写，也是说的用maxflow去做 (0) frkstyc 2005-05-19 14:11:53
          • 用匈牙利怎么求最小覆盖啊？ (0) js05 2005-05-19 15:06:35
      • 谁说preflow慢了？看我的1459 109ms，还是用了STL的 (4) frkstyc 2005-05-19 13:54:01
        • 我是指preflow做匹配...... (0) TN 2005-05-19 14:02:55
          • 邻接表的匈牙利是相当快的~~~ (0) palmtenor 2005-05-19 19:45:30