最小カット:すべてがTrueまたはFalseのときの利得を表す
最小カット:PSP(燃やす埋める)
【問題集】フローのステップアップ
最小カット
テーマ解説記事
最小カット:すべてがTrueまたはFalseのときの利得を表す
最小カット:3変数劣モジュラ関数
最小カット:PSP以外の2変数劣モジュラ関数
競プロにおいて、「Project Selection」や「2 変数劣モジュラ関数の和の最小化」などと呼ばれるテクニックがあります。いずれも、最小カット問題に帰着して解くことができます。これらは次のような関係にあります。なお、俗に「燃やす埋める」と呼ばれている…
AtCoder
AtCoder625点
ABC-G
橙色diff
最小カット
フロー
【問題集】フローのステップアップ
マトロイドと劣モジュラ関数
グラフ
スイッチ
最小カット:K値変数をK-1個の0-1変数で表す
最小カット:PSP(燃やす埋める)
最小コスト
最小カット:すべてがTrueまたはFalseのときの利得を表す
最適化問題
2 変数劣モジュラ関数の和の最小化を最小カットにするやつ！ 問題へのリンク 問題概要 種類のスキルがある。それぞれ初期状態のスキルレベルは 1 であるが、最大で 5 まで上げられる。スキル のスキルレベルを 1 上げるのに必要なコストは 円である。 種類の…
AOJ
RUPC
フロー
グラフ
二次元グリッド
タイリング
最小カット:PSP(燃やす埋める)
最小カット
有志コン
けんちょん本演習問題
思わず解きたくなる興味深い良問
【問題集】フローのステップアップ
【問題集】フローのチャレンジ
解空間:O(2^N)通りの選択肢
マトロイドと劣モジュラ関数
最小コスト
そのまま覚えたいシンプル設定の中堅以上の典型問題
最小カット:PSP以外の2変数劣モジュラ関数
最小カット:すべてがTrueまたはFalseのときの利得を表す
最適化問題
2 変数劣モジュラ関数の和を最小カットで表すという、とても面白い問題！！！ 問題へのリンク 問題概要 × の二次元ボードが与えられる。以下のような "#" のところを最小個数の長方形で敷き詰めよ。例えば 4 10 ########## ....#..... ....#..... ..........…
