Rabbit Walking (AOJ 2370)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2370

問題

略

解法

まずグラフを2彩色出来なければ答えは-1になる。2彩色できたら各連結成分に白の数と黒の数のminと差を記憶しておく。追加する辺の数を最大にするには2部グラフの片側に何個頂点を置くことが出きるかを計算しなければならない。これは差が個しか無い*1ので、種類の物の使える個数が決まっているナップサック問題を解けばで解ける。

*1:以下の物は当然個しか無く、以上の物は合計値がn以下であるので個しか無い