AOJ 2370: RabbitWalking

,

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

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;
}