aoj2370:RabbitWalking
解法
奇数長の閉路が存在しない<==>二色彩色可能<==>二部グラフ
みたいなやつがあります。(昔どこかのコンテストでこれ知らなくて全然解けなかった思い出がある)
よって、まずは二色彩色をしてみます。この時点で不可能なら、-1を出力します。
各連結成分ごとに、(黒の数、白の数)を計算します(黒と白の二色で彩色したとする)。
連結成分内のすべての頂点の色を反転させても二色彩色された状態は保たれるので、黒の数と白の数は入れ替えることができます。
このとき、(全体の黒の数)*(全体の白の数)-Eを最大化したくなります。
当然全探索(各連結成分ごとに色を反転するかどうかを割り当てていくO(2^(連結成分の数))の全探索)は不可能。そこでdpをしていく。
dp[i][j]:=i番目の連結成分までみて、黒に塗られた頂点の数がj個、という状況にできるかどうか(bool)(白に塗られた頂点の数は、iとjが定まれば一意に求まるので覚えなくていい)
として、適当にやればO(N×(連結成分の数))。これは、ケースによってはO(N^2)みたいになって死ぬ。
でもbitset並列化すれば通る(ダメ)。
正直bitset並列化が想定解じゃなさそうな問題をbitsetで通すと、勉強の機会を逃す感じがあってあれですね(たまに本当にbitset想定みたいなのがあって、競プロって難しいなあみたいな気持ちになる)
想定解(本当に想定解かどうかは知らないが、ちゃんとオーダーが落ちてそこそこきれいな解)をググって見つけたので、一応書きます(cosさんのブログをみました)。
頂点の数がsqrt(N)以下の連結成分は当然O(sqrt(N))種類くらいあって、頂点の数がsqrt(N)より大きい連結成分の数は、O(sqrt(N))個程度しかない。
(前者は「種類」がO(sqrt(N))程度であるのに対し、後者は「個数」がO(sqrt(N))個くらいしかない。まあ特にこの違いが重要になってくるわけではないが、一応)
同じサイズの連結成分についてはまとめてdpを回せる(蟻本のdpのところに、個数制限付きナップザック問題みたいなやつがあります)
全体でO(sqrt(N))種類くらいしかないので、計算量はO(Nsqrt(N))。
