コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
供養
解法
- $v_{i}, w_{j}$ 間に重み $B_{v_{i}, w_{j}}$ の辺がある二部グラフ $G = (V, W, E)$ を考える
- $B_{v_{i}, w_{j}} = 0$ のとき、$v_{i}, w_{j}$ 間に辺はないものとする
- $G$ の各点の要素数は行 $v_{i}$ もしくは 列 $w_{j}$ における修復が必要な要素数となる
- 孤立点ならば行 $v_{i}$ もしくは 列 $w_{j}$ のすべての要素が明らかになっている
- 葉ならば行 $v_{i}$ もしくは 列 $w_{j}$ において1つだけ修復が必要な要素がある
- $R_{v_{i}}$ もしくは $C_{w_{j}}$ を使うことで修復することができる
- $E$ からいくつかの辺を取り除いた $G^{'}$ が森であるならば、葉である点を端点にもつ辺を削除していく操作を繰り返すことですべての要素を修復できる
- したがって、$G$についてのMaximum Weight Forestを作れば、その重みの合計 $W$ について $\sum_{i = 1}^{N}\sum_{j = 1}^{N}B_{i, j} - W$ が最小コストになる
- $E$ の辺を重みについて降順に見たときに、辺を追加することでサイクルにならない限り辺を追加していく操作をすればよい
- サイクル判定はUnion-Findなどで実現可能
計算量はテストケースあたり $O(N^{2}\mathrm{log}N)$
公式解説
躓いた点
