没消负圈哈，用Johnson算法reweight了的。。
我目前还只知道朴素的primal-dual实现，我估计不出复杂度，应该不是教主想要的O(n^3)的。。。

这题我就是写的SSP，的确效果还比较好，不知道放个Dinic进去把搞成primal-dual会是什么样子。。
还有就是，为什么这题ssp好点呢？？

• 汗，你怎么知道我想要的是O(V^3)的原始对偶，强…… (95) wywcgs 2007-10-23 12:43:26
  • 大家都知道教主对算法很挑剔的，所以能吸引住教主的原因就必然是一个复杂度里没有不干净的东西的费用流实现。。 (40) richardxx 2007-10-23 14:26:22
    • 我也很想知道是怎么实现的…… (36) wywcgs 2007-10-23 15:06:58
      • 恩，受教了，期待loard wu有一天能带着O(n^3)回POJ发贴。。 (40) richardxx 2007-10-23 15:48:29
        • 然后瞬间被frjj阉了？say,别在这贴代码XD (0) MrRight 2007-10-23 15:56:11
  • UVA10594 leemars的primal-dual比我的succesive快…… (101) frkstyc 2007-10-23 18:15:46
• ssp对哪类图效果会比较差呢？ (172) MrRight 2007-10-23 14:37:15
  • 不清楚，毕竟是伪多项式算法，实现得再好 tle我都不惊讶-_- (0) wywcgs 2007-10-23 15:05:42