AOJ 2370: RabbitWalking
solution
$2$部グラフを利用。bitset
による定数倍高速化。$O(V^2)$。
奇閉路が存在しない $\iff$ $2$部グラフ。
各連結成分$i$について$2$色彩色可能かを調べ、それぞれで$(A_i, B_i)$の頂点集合の組に分ける。
全体を$2$部グラフ$(A, B)$にするように合成するが、このとき$|A| - |B|$が小さくなるように分けたい。
これはDP。同じ大きさのものをまとめて個数制限付きのknapsack問題とすれば$O(\sqrt{V})$で解けるようだが、bitset
による愚直$O(V^2)$でも間に合う。
implementation
#include <algorithm>
#include <cstdio>
#include <bitset>
#include <functional>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
constexpr int max_v = 100000;
int main() {
// input
int v, e; scanf("%d%d", &v, &e);
vector<vector<int> > g(v);
repeat (i, e) {
int a, b; scanf("%d%d", &a, &b); -- a; -- b;
g[a].push_back(b);
g[b].push_back(a);
}
// solve
bool is_impossible = false;
vector<pair<int, int> > component_size; {
vector<char> color(v);
function<bool (int, char, int &, int &)> go = [&](int i, char c, int & red_count, int & black_count) {
if (color[i]) return color[i] == c;
color[i] = c;
(c == 'R' ? red_count : black_count) += 1;
char d = c ^ 'R' ^ 'B';
for (int j : g[i]) {
if (not go(j, d, red_count, black_count)) {
return false;
}
}
return true;
};
repeat (i, v) if (not color[i]) {
int red_count = 0;
int black_count = 0;
if (go(i, 'R', red_count, black_count)) {
component_size.emplace_back(red_count, black_count);
} else {
is_impossible = true;
break;
}
}
}
ll result = -1;
if (not is_impossible) {
bitset<max_v+1> dp = {};
dp[0] = true;
for (auto it : component_size) {
int a, b; tie(a, b) = it;
dp = (dp << a) | (dp << b);
}
repeat (a, v+1) if (dp[a]) {
ll b = v - a;
setmax(result, a * b - e);
}
}
// output
printf("%lld\n", result);
return 0;
}