inarizuuuushi https://blog.hatena.ne.jp/inarizuuuushi/ Sabrou-mal サブロウ丸 https://inarizuuuushi.hatenablog.com/ グラフ理論 次のようなネットワークのフロー分解を考えます。 まず、フローとは何かという話ですが、 始点(図s)から終点に(図t)に水を流すことを考えます。 そのときの"水の流れ"のことをフローと呼びますが、それにはいくつか条件があります。 図のノード(丸)とノードを結ぶ矢印の方向に管があり、それを伝って矢印の方向に水が流れるのですが、それぞれの管に流せる水の最大量が決まって、管に流せる量よりも多くの水は流せません。 またそのときにs, t以外のノード(図1~4)では 水の流入量と流出量が等しくなってなければなりません。(例えばノード1では流入量は3 + 2 = 5で流出量は1 + 4 = 5) 以上の性質… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finarizuuuushi.hatenablog.com%2Fentry%2F2017%2F04%2F30%2F090419" title="フロー分解 - Sabrou-mal サブロウ丸" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/i/inarizuuuushi/20170420/20170420200053.png Hatena Blog https://hatena.blog 2017-04-30 09:04:19 rich https://inarizuuuushi.hatenablog.com/entry/2017/04/30/090419 1.0 100%