unageanu https://blog.hatena.ne.jp/unageanu/ うなの日記 https://unageanu.hatenablog.com/ フォード・ファルカーソンのアルゴリズム で、ネットワークの最大フローを算出してみます。 最大フローとは 以下のようなそうめん流しシステム(=ネットワーク)があるとします。 「→」は「竹とい」を示します。「○」は、「竹とい」の接点。 「→」の横の数値は、1分間に転送可能なそうめんの量を表します。 このシステムで、「1分間に 任意の二点間(例: a→f) に転送可能な最大そうめん量」が「最大フロー」となります。 ネットワークのデータ構造 例によって、構築と探索に必要な最低限の機能のみ用意。 Networkは、頂点(Vertex)と、頂点と頂点を結ぶ辺(edge)を持ちます。 各辺は「capacit… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Funageanu.hatenablog.com%2Fentry%2F20110822%2F1313989323" title=" [Ruby] フォード・ファルカーソン法でネットワークの最大フローを求める - うなの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://cdn-ak.f.st-hatena.com/images/fotolife/u/unageanu/20110822/20110822135548.gif Hatena Blog https://hatena.blog 2011-08-22 14:02:03 rich https://unageanu.hatenablog.com/entry/20110822/1313989323 1.0 100%