ARC099 E - Independence
解法
頂点と
の間に辺が張られていない場合、これらを同じ州に含めることができません。
これは全ての張られていない辺について成り立ちます。逆に、同じ州に含めることができない頂点対に辺を張ったグラフを考えると(これは与えられるグラフの補グラフです)、それぞれの連結成分が二部グラフになっている必要があることがわかります。
ということで、まず構築できる条件がわかったのでチェックします。
二部グラフ判定は、補グラフについてワーシャルフロイドを適用した後、全ての頂点のタプルについて、
と
の距離の偶奇が、
から
の距離と
から
の距離の和の偶奇と一致しているかどうかを見ればよいです。
さて、辺の数を最小にする問題を考えます。
ある州に個の頂点を含ませた場合、そこに存在する辺の本数は
です。また、もう片方の州は個の頂点が存在しているはずで、こちらも同様に辺の本数を数えることができます。
ということで、州の個数がにできるかどうかを判定し、できる個数のうち辺が最小のものを選べば答えとなります。
あとは、個からなる州が作成可能かどうかわかればよいです。
先ほどの補グラフに再び注目します。
ある連結成分についてみると、二部グラフの頂点のグループは一意に定まります(適当な頂点からの距離を調べ、偶奇でグループ分けすればよいです)。
ですが、どちらのグループを州に含めるか、というのはそれぞれの連結成分ごとに自由に決められます。
ということで、
番目の連結成分までみて、
個からなる州の集合が作成可能かどうか(bool値)
というdpが考えられます。
今見ている連結成分のグループの個数のペアがだった際、
という遷移を行えばよいです。
これで、作成できる州の頂点数がわかったので、あとは最小値を計算すれば終わりになります。
感想
補グラフと二部グラフがうまく考察できたので嬉しいです。面白かったです。
