最小カット:二部グラフであることを活かした変数変換
最小カット:PSP(燃やす埋める)
最小カット
最小カット:二部グラフであることを活かした変数変換
最小カット:変数変換によって劣モジュラ関数にする
最小カット:K値変数をK-1個の0-1変数で表す
フロー
【問題集】フローのステップアップ
【問題集】フローのチャレンジ
グラフ
AtCoder
AtCoder800点
ARC-E
赤色diff
数列
操作
操作:chmax
値A[i]を頂点に持たせたグラフを考える
面白かった!! 上手に変数変換することで「2 変数劣モジュラ関数の和の最小化」になるタイプの問題だった。 問題へのリンク 問題概要 考えたこと 一目見て、2 変数劣モジュラ関数の最小化 (燃やす埋める) っぽいと感じた。値が 500 以下というのも怪しい。 …
AOJ
RUPC
最小カット:PSP(燃やす埋める)
最小カット
フロー
グラフ
二部グラフ
二部グラフであることを活かした変数変換
条件の言い換え
二次元グリッド
最大スコア
最小コスト
【問題集】フローのステップアップ
解空間:O(2^N)通りの選択肢
中堅以上の典型要素を詰め合わせた教育的問題
マトロイドと劣モジュラ関数
最小カット:二部グラフであることを活かした変数変換
最適化問題
燃やす埋めるは今度こそちゃんとマスターする!!! 問題へのリンク 問題概要 × の各格子点に電球がある。 が偶数となるような について、 を頂点とする正方形の中心に装置があって、各装置を押すことで四隅の電球を点灯することができる。 ただし、装置を起…