高速な最大流アルゴリズム(Dinic法) - tomiflu's blog
2012-12-03 高速な最大流アルゴリズム(Dinic法) PKU Tips Dinic法 Ford-Fulkerson法は計算量がO(F|E|)だった。多くの場合にはこのアルゴリズムで十分だが、頂点数や流量が非常に大きかったりする場合で速度が不十分な場合がある。 実は、最大流問題を解くアルゴリズムは他にも非常にたくさんあり、その中でも実装が比較的簡単で実用上の速度が非常に優れているDinic法を紹介する。Ford-Fulkerson法では深さ優先探索で増加パスを探し、そこにフローを流していた。これに対しDinic法では最短の増加パスを探して、そこにフローを流していく。 最短の増加パスの長さは、フローを流すことで短くなることはないから、毎回幅優先探索を行って最短路を求めるのではなく、一度幅優先探索を行い、距離が増加する向きの辺のみからなるグラフを作成した上で、深さ優先探索を行う。
強連結成分分解 - Win The Game
蝶本, Tips 強連結成分有向グラフにおいて、頂点の部分集合Sが「任意の２頂点u,vをとったとき、uからvへ到達できる」とき、Sは強連結であるという。 頂点の強連結な集合Sに、他のどの頂点集合を付け加えても強連結にできないとき、Sを強連結成分(SCC:Strongly Connected Component)という。 また、任意の有向グラフはいくつかの強連結成分の、共通部分を持たない和集合に分解することができる。 強連結成分分解任意の有向グラフをいくつかの強連結成分の、共通部分を持たない和集合に分解すること。 強連結成分を１つの頂点につぶすｋとで、DAG(閉路をもたない有向グラフ)になる。 強連結成分分解は２回の簡単なDFSで行うことができる。 １回目のDFSでは、適当な頂点からはじめ、まだ通っていない頂点を帰りがけの順で番号をつけていく。まだ通っていない頂点がある場合は、再びそこからは
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
