フローを流す際にバイパス辺を用意する
AtCoder
ACLpractice
二次元グリッド
可視化テク:二次元情報を二部グラフにして考える
二部グラフ
マッチング
二部マッチング
フロー
そのまま覚えたい典型問題
最小費用流問題
N個からK個を選ぶ設定の問題
順列の最適化問題
順列を題材とした問題
最大スコア
制約条件:K個以下
復元
どれか1つ求める
最適化テク:解を変形していく(最適性を失わずに)
下駄を履かせて負辺除去
フローを流す際にバイパス辺を用意する
解空間:O(N!)通りの選択肢
【問題集】フローの入門
最適化問題
D 問題の MaxFlow に続いて、これまた、人生で一度は解くべき超典型問題ですね。そして、D 問題とは違うやり方で、二部グラフを作ることにも注目です! 問題へのリンク 問題概要 のグリッドがあり、各マスには数値が書かれています。 これらのマスからいくつ…