二部グラフであることを活かした変数変換
Codeforces
EducationalCodeforces
二部グラフ
フロー
最小費用流問題
需要供給制約付きフロー問題
条件の言い換え
二部グラフであることを活かした変数変換
グラフ
復元
下限流量制約付きフロー
CodeforcesR2900
需要と供給に関する問題
【問題集】フローのチャレンジ
需要供給を考え、さらに最小流量制約もある最小費用フロー！！！ 問題へのリンク 問題概要 左頂点数 、右頂点数 、辺数 の二部グラフが与えられる。各頂点は「赤」または「青」または「白」に塗られている。 さて、各辺は最初は白色である。そのうちの何本か…
AOJ
RUPC
最小カット:PSP(燃やす埋める)
最小カット
フロー
グラフ
二部グラフ
二部グラフであることを活かした変数変換
条件の言い換え
二次元グリッド
最大スコア
最小コスト
【問題集】フローのステップアップ
解空間:O(2^N)通りの選択肢
中堅以上の典型要素を詰め合わせた教育的問題
マトロイドと劣モジュラ関数
最小カット:二部グラフであることを活かした変数変換
最適化問題
燃やす埋めるは今度こそちゃんとマスターする！！！ 問題へのリンク 問題概要 × の各格子点に電球がある。 が偶数となるような について、 を頂点とする正方形の中心に装置があって、各装置を押すことで四隅の電球を点灯することができる。 ただし、装置を起…
DFS
連結成分
二次元グリッド
パリティ
Union-Find
BFS
AtCoder300点
AtCoder
水色diff
ABC-like
連結成分ごとに分解して考える
【問題集】DFS・BFSのステップアップ
二部グラフ
二部グラフであることを活かした変数変換
市松模様・塗り分け
解空間:O(N^2)通りの選択肢
DP とかメモ化再帰とか考え出すとドツボにはまる...素直な考察が大事だね。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは白か黒で塗られている。「黒」マスと「白」マスのペアであって、 黒マスから出発して、隣接するマスを辿っていくことで…
