気に入った記事をブックマーク
- 気に入った記事を保存できます
保存した記事の一覧は、はてなブックマークで確認・編集ができます
- 記事を読んだ感想やメモを書き残せます
- 非公開でブックマークすることもできます
エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
0
記事へのコメント0件
- 注目コメント
- 新着コメント
新着コメントはまだありません。
このエントリーにコメントしてみましょう。
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
いまの話題をアプリでチェック！
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Spaghetti Source - 最大流 (Edmonds-Karp)
目的 Edmond-Karp は最短路反復によって最大流問題を解くアルゴリズムである． 始点から終点までの(辺の... 目的 Edmond-Karp は最短路反復によって最大流問題を解くアルゴリズムである． 始点から終点までの(辺の本数の意味での)最短路を求め，そこにフローを流す．到達不能になるまでこれを繰り返す．整数フローの場合は必ず停止するが，実数フローの場合止まらないケースが存在する． 最大流最小カット定理によって，最大流が求まったとき同時に最小カットも求まっている． プログラミングコンテストで出るような問題であればこれでほとんどの場合十分であるが，速度が問題になる場合は一段高速なアルゴリズム（Dinic，Goldberg-Tarjan）を検討することになる． 計算量 O(E^2 V)．以下の実装では内部で隣接行列を生成するため，O(V^2) の追加コストがかかっている． ソースコード #define RESIDUE(s,t) (capacity[s][t]-flow[s][t]) Weight ma
