haraduka https://blog.hatena.ne.jp/haraduka/ haraduka's diary https://haraduka.hatenadiary.jp/ 蟻本 試験が残り一つなので適当に蟻本を読んでみることにした。 最大流 …グラフにおいてs(source)からt(sink)に水を流したときに最大どのくらい流せるか？蟻本にのっていたように、最初にdfsでsからtまで限界まで水を流す。 その後、水を押し戻したりして最大になるように頑張る、というのが基本。ちゃんとした言葉にすると、f(e)をフロー、c(e)をcapacityとすると、f(e) 0である辺の逆辺を用いて(このようなグラフを残余グラフという)dfsをすれば良い。これだけである。(Ford-Fulkersonの定理) また、これを証明するのに最小カットという概念を使う。 最小カット …グラフに… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fharaduka.hatenadiary.jp%2Fentry%2F2015%2F07%2F19%2F143349" title="最大流と最小カット - haraduka&#39;s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-07-19 14:33:49 rich https://haraduka.hatenadiary.jp/entry/2015/07/19/143349 1.0 100%