週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

共立出版工系数学講座 グラフ・ネットワーク・組合せ論のDinitz(Dinic)のアルゴリズムは最適じゃない気がします。正しいけど少し遅い。 この本だと距離ラベルをsourceからの距離で計算しています。逆に、sinkからの距離で計算したほうが速いのではないかと思うのです。こっちだとdfsのときにフローが確実にsinkへ流れてゆきます。sourceからの距離で計算するとフローが行き止まりに突き当たってバックトラックすることが多くなります。もちろん、一回バックトラックした枝は切除していいのでそれほど遅くなるわけではありませんが。

雑な例で調べたら等倍~二倍程度の速さでした。自信を持って速いといえるほど速くないです。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/353-8b754637
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。