Disconnected Game (AOJ 2376)

AOJ Online Judge

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

問題

略

解法

dp[odd][even][e]を計算して解く。oddは頂点の数が奇数の連結成分の個数、evenは頂点の数が偶数の連結成分の個数、eは連結成分内でまだ使用してない辺の個数の偶奇を表す。eの部分でループが発生するが、eが偶数から奇数へ変化する場合を考慮すると、最善手がその手で有った場合、相手も同様の手を選ぶので辺の個数が0になってそのような手を選べなくなるので問題ない。あとは入力のグラフの頂点と連結成分の個数を調べ初期状態を決めれば良い。
現在AOJとJAGの元データの出力が間違っている*1ので注意。

(追記)AOJは白旗になった。
(追記)AOJは修正された。

*1:初期状態の辺の数を偶数とすれば一致する