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