jeneshicc https://blog.hatena.ne.jp/jeneshicc/ 落書き、時々落学 https://jeneshicc.hatenadiary.org/ 日記 C++ algorithm 最小費用流実装した． 最小費用流のアルゴリズムは少なくとも3種類ぐらいある． とりあえず，フローを求めてから，負閉路を頑張って消していく 最小費用0フローからはじめて，augmenting shortest path で増やしていく push, relabelの一般化（よく知らない） 2番目を実装した．簡単のため，非負費用．検証は UVa 10594 Data Flow.適当に組んだら時間オーバーだったので，配列とか使って真面目に書いた．本体は以下．非負費用というのが大きい．まず，f=0が最小費用0フローになっている． よって，ポテンシャルの決定にベルマンフォードを実行しなくて良い． ただ，単… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjeneshicc.hatenadiary.org%2Fentry%2F20100225%2F1267053748" title="最小費用流 @ C++ - 落書き、時々落学" 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 2010-02-25 08:22:28 rich https://jeneshicc.hatenadiary.org/entry/20100225/1267053748 1.0 100%