komiyam https://blog.hatena.ne.jp/komiyam/ komiyamの日記 https://komiyam.hatenadiary.org/ アルゴリズム 様々な問題をLPやその双対を駆使して解きまくっているwataさんが格好良すぎるので、ちょっといくつかの最小カットの問題を解き直してみた。 私はLPにも最大流にも詳しくないので、完全ユニモジュラとか言われても「成り立ってることを祈りましょう」くらいしか言えないし、どこがLPなんだよ！と言われてもまともに答えられる自信はないです。 基本形 x[i]は0または1の値をとり、x[s]=1,x[t]=0とする。関数f(x)=x>0?1:0と定義したとき、sum f(x[i]-x[j])*c[i][j]の最小化問題でかけるもの。ただしc[i][j]>=0。具体的にグラフを構成するにはiからjへ容量c[i]… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkomiyam.hatenadiary.org%2Fentry%2F20121208%2F1354895372" title="LPっぽいのと最小カット - komiyamの日記" 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 2012-12-08 00:49:32 rich https://komiyam.hatenadiary.org/entry/20121208/1354895372 1.0 100%