Hatena::Grouptopcoder

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

 | 

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

■ 結論 02:05

ワーストケースはマジ死ぬ.

Dinic 法は使い所を間違えると辛い事になる.

例えば, 次のような条件が揃うとヤバめ.

  1. 問題の入力をうまくすれば, 最大流を求めなきゃいけないグラフを, 割と自由に決められる.
  2. 頂点数が 500 以下 みたいな, Dinic 法とかを過信した制約.

こういう時は, Goldberg-Tarjan とか, Push/Relabel 系のアルゴリズムを使った方がよさげ.

逆に,

  • 問題の入力から, 特殊な形のグラフを作って, その上で最大流を求める.

の場合は, 割と制約大きくても, Dinic のワーストケースを突くのが難しく, 大丈夫そう.

特に, 前に言った, 辺容量が全て同じ場合や, 二部グラフの場合など.

コメントを書く

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 ですが)そのとおりですね. ご指摘ありがとうございます, 修正します.

 |