競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2306 Rabbit Party

解法

全然関係ない話をすると,グループに含まれる頂点集合からなる完全グラフのMSTのスコアがそのままそのグループのスコアになる(本当に関係ない)

グループが既にあったとして,そのグループに一人追加することを考える.このとき,元のグループのある人と新しく追加する人の間に関係がなかった場合,新しく追加する人のスコアは0になるし,他の人のスコアが増えることはない.
つまり,最適な頂点集合は与えられた辺で完全グラフを構築できる必要がある.
辺の数は100以下なので,選ぶことのできるグループはかなり限られる.
というわけで適当に完全グラフを保ちつつ一人ずつ追加していく全探索を適当にしてやれば通ります.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1926065#1
計算量なんてなかった.間に合う自信はあったけど計算量の見積もりがしづらい