真折腾人~~~~~
以后最大流还是少用邻接表……

• re (31) wanpiOuser 2005-12-09 15:32:28
• ve^2 和 ev^2 差别不大， 是 ev^2 的常数太大么？ (31) semonteer 2006-03-25 22:13:11
  • 是很多情况下达不到这个数 (0) frkstyc 2006-03-25 22:34:57
    • 加个 当前弧， 就过不了了， 时间上基本没变化 (0) semonteer 2006-03-26 00:16:44
• 为什么，我在本地测试的时候，通过调整参数，二者相差10多倍的效率，交上来只差 30 ms, 而且一般预流推进应该比距离标号最短增广路至少差10的常数，是我做的不对么？ (31) semonteer 2006-03-26 12:18:52
  • 这个题体现不了 HLPP 的速度么？ 用 HLPP 速度不如 GB_SA，和 General Preflow Push 基本一样 (0) semonteer 2006-03-26 22:41:25
    • LTC的15ms (0) frkstyc 2006-03-26 22:42:27
      • 不敢和 LTC 比， 对于大多数人来说吧 (0) semonteer 2006-03-26 22:44:21
        • 优化过的先流推进可以的确很快 (0) frkstyc 2006-03-26 22:46:54
          • 大多数的资料，基本说了三点优化， 邻接表（这个不好用），当前弧， 标号链表， 自己没能力想优化了，请问怎样能优化 (0) semonteer 2006-03-26 22:50:31
            • up (0) semonteer 2006-03-27 18:48:04
• up (31) semonteer 2006-03-26 23:30:43
• 做了一个 O(e*log(f)) 的 EK 最大瓶颈增广路算法, 结果效果不好 对于这个题目, log(f)应该不大于32, 效率应该很高才对啊 (31) semonteer 2006-06-27 22:38:34
  • 大O记号的意义你理解么？ (0) frkstyc 2006-06-27 22:39:42
    • 不了解 (0) oeym 2006-06-27 22:41:16
    • 常数的问题, 了解一些 (0) semonteer 2006-06-27 22:42:55
    • 那么也就是说如果规模更大些, 才能体现出优势? 这个算法也称作伪多项式算法么 (0) semonteer 2006-06-27 22:56:41
      • 这个很难说的，要让时间达到bound往往需要一些特殊的网络 (0) frkstyc 2006-06-27 23:11:24
    • 您好, 我想了一下, 书上说 最多进行log(f)次迭代,f是最终的最大流数值, 每次迭代O(e), 然后对比一下,和我以前的程序相比,常数应该说比较小,我也是用类似prim的贪心法找最大瓶颈路,指点一下吧 (1395) semonteer 2006-06-27 23:16:34
      • 我记得capacity scaling是O(E^2lgC)的吧 (1491) frkstyc 2006-06-27 23:27:58
        • 要进行 e*log(c) 次迭代? (0) semonteer 2006-06-27 23:31:26
        • sorry 我错了 (0) semonteer 2006-06-28 00:01:50
          • 为什么这么菜... (0) semonteer 2006-06-28 00:02:06
• Re:开始用邻接表做本题就超时，改成邻接矩阵做就AC了~~ (17) saintqdd 2010-03-31 21:55:39
  • Re:开始用邻接表做本题就超时，改成邻接矩阵做就AC了~~ (35) lyzardiar 2011-03-14 13:07:49