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 c0500301036 at 2005-05-17 15:59:08 on Problem 2239

Followed by:

难道不是匹配吗？ (0) TN 2005-05-17 17:20:40
- 怎么我的二分图匹配这么慢啊，6**MS (0) c0500301036 2005-05-17 19:22:48
- 我是菜鸟，大家帮帮忙，二分图匹配是不是用网络流做的啊？ (16) c0500301036 2005-05-18 17:00:44
  - 用匈牙利算法。。。 (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
推荐大家去做这个题目：）1815。这个题目对网络流的速度还有有一点点要求得：） (2) LiHaoyuan 2005-05-19 21:00:09
- for_test come on:) (6) LiHaoyuan 2005-05-21 00:44:42
大家不会嫌我唠叨吧？网络流的问题就一并问了：求最大流是只能用O(n^4)的可增广轨的方法吗？ (0) c0500301036 2005-05-20 13:59:30
- highest label preflow push是O(V^2*E^(1/2)) (0) frkstyc 2005-05-20 14:00:30
- 现在最强的最大流好象是eloge的，完全看不懂。。。 (0) js05 2005-05-20 14:24:15
  - 也有可能是v^2loge的，记得不怎么清楚了。。。 (0) js05 2005-05-20 14:24:50
  - 临场写得出来才有用的，HLPP就很不容易写了，还要搞ElogE的，估计赛场上大家都写的FF或者EK了吧？ (0) frkstyc 2005-05-20 14:26:10
弱弱的问一句,啥叫匈牙利算法 (28) uni 2005-05-21 01:02:31
- 求二分图最大匹配的O(mn)，king's quest怎么做？ (32) frkstyc 2005-05-21 01:55:37
  - Re:求二分图最大匹配的O(mn)，king's quest怎么做？ (42) uni 2005-05-21 14:38:39
    - 1904和1466好像是两个互逆的问题，是吧？ (48) frkstyc 2005-05-21 14:42:35

Post your reply here:

Home Page Go Back To top