Hatena::Grouptopcoder

れんしゅうちょう。 このページをアンテナに追加 RSSフィード

 | 

2014-03-11最大流問題について.

参考文献 02:05

1. は Yefim Dinitz の一番上から読めます.

2. は Worst case behavior of the Dinic algorithm から読めます.

3. は Maximum Flow: Augmenting Path Algorithms Comparison – topcoder.

  1. Yefim Dinitz (2006), Dinitz' algorithm: the original version and even's version, In Theoretical Computer Science, Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (Eds.), Springer-Verlag, pp.218-240.
  2. Gary R. Waissi (1991), Worst case behavior of the Dinic algorithm, Applied Mathematics Letters, vol.4, no.5, pp.57-60
  3. Zealint, Maximum Flow: Augmenting Path Algorithms Comparison, Algorithm Tutorials, TopCoder
  4. 秋葉拓哉, 岩田陽一, 北川宜稔 (2012), プログラミングコンテストチャレンジブック-第2版-~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~, マイナビ

7747742015/10/15 23:28「Dinic 法と, その注意点」の注意2の部分について
探索順序は
S, a, b, a, e, a, S, b, e, b, f, b, S, c, g, T, g, c, h, T, h, c, S
ではないですか?最初に g に来たときに c に戻るのはなぜでしょうか.
私が理解していない/勘違いしていたら済みません.

Mi_SawaMi_Sawa2015/10/15 23:39(最初の b が d ですが)そのとおりですね. ご指摘ありがとうございます, 修正します.

 |