オンサイトで未確認

ukuku09の活動記録。

AOJ 2370: RabbitWalking

久しぶりにブログを書くわ!自分用メモだけど。

 

問題概要

RabbitWalking | Aizu Online Judge

 

解法

まず"-1"の判定ですが、グラフが奇閉路を含まないことと二部グラフであることは必要十分条件なので、与えられたグラフの各連結成分が二部グラフであるかどうか判定します。もし二部グラフでない連結成分が一つでもあったら"-1"です。

二部グラフ判定はUnionFindやDFSを使って判定できますが、今回は後から各連結成分の各色(ここでは黒と白とします)の個数を利用したいので、DFSで2彩色しながら個数を数えるのが良いと思います。

(後述しますが、正確には各色の個数というより、二部グラフを構成する2つの頂点集合の大きさが必要になります)

 

もしすべての連結成分が二部グラフである場合、辺を0本以上追加して二部グラフを保ったまま各連結成分を連結することができます。

課題から、辺の追加本数を最大化したいので、各連結成分は完全二部グラフにしてしまって良いことが考察できます。さらに、各連結成分を連結してできる二部グラフもまた完全二部グラフにできます。

完全二部グラフの辺の本数は(黒の個数)*(白の個数)なので、結局(各連結成分の黒の個数の和)*(各連結成分の白の和)を最大化すると良さそうです。

 

先ほど各連結成分ごとに適当に2彩色しましたが、連結成分内ですべての頂点の色を反転させても2彩色状態は保たれるので、二部グラフの2つの頂点集合の大きさのみに注目します。

今、いくつかの連結成分を連結してできた完全二部グラフ$K_{n_i,m_i}$と、まだ連結していない連結成分$K_{a_j,b_j}$を連結すると、新たな完全二部グラフとして、$K_{n_i+a_j,m_i+b_j}$または$K_{n_i+b_j,m_i+a_j}$を得ることができます。このようにして得られる完全二部グラフ$K_{n_k,m_k}$における$n_k*m_k$の最大値が求めるべき解です。(あとで元からある辺の数$E$を引きます)

(2つの頂点集合$V_1,V_2$の大きさをそれぞれ$x,y$とする完全二部グラフを$K_{x,y}$と表記しています)

 

これを解くために次のようなDPを考えてみます。

$dp[i][j][k]:=i$番目までの連結成分を用いて$K_{j,k}$を作ることができるか

これを計算すると、$dp[V][j][k]==true$を満たす$j,k$の積の最大値が解となります。

さらに、$k$の最適値は$i$と$j$がわかれば一意に定まるので、$dp[i][j]$としてしまっても良さそうです。しかし、このDPでは計算量が$O(V^2)$になってしまうので当然間に合いません。

 

計算量を落とすためのアイデアとして、各連結成分$K_{a_j,b_j}$における2つの頂点集合の大きさの差分$abs(a_j-b_j)$($c_j$とします)と、$Σmin(a_j,b_j)$($L$とします)を考えます。すべての連結成分を用いてできる完全二部グラフは、どちらの頂点集合の大きさも必ず$L$以上になっているはずです。また、完全二部グラフの$V_1$の大きさの増分はいくつかの$c_j$の和$sum$として表すことができます。全体の頂点数は$V$なので、この完全二部グラフは$K_{L+sum,V-L-sum}$となります。($a_j>b_j$なら、$n_k$に$a_j$を足して$m_k$に$b_j$を足すのは、$n_k$に$b_j+c_j$を足して$m_k$に$b_j$を足すと見なせます)

(補足ですが、求めるべき完全二部グラフは必ずすべての頂点を含んでいます。これは、完全二部グラフの2つの頂点集合の大きさが連結に伴って単調増加するためです)

 

したがって、先のDPは次のように書き直すことができます。

$dp[i][j]:=i$番目までの差分を用いて$j$を作ることができるか

さらに、$c_j$の種類数は$O(√V)$程度に収まるので、個数制限付き部分和問題(詳しくは蟻本P62参照)と見なして$O(V√V)$で解くことができます。

 

gist85ccc57cc00c88617e78bccfb8de48fc

 

すごく冗長、しかも変数や添字が最高にわかりづらいわ…。はぁ〜、なんて悪魔的なのかしらぁ〜!