けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2370 RabbitWalking (JAG 冬合宿 2010 day3-B) (600 点)

これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。

問題へのリンク

問題概要

 V 頂点  E 辺の無向単純グラフが与えられる。
このグラフが「奇数長のサイクルがない」という状態を保ちつつ、最大本数の辺を追加せよ。最初からそうでない場合は -1 をリターンせよ。

制約

  •  1 \le V \le 10^{5}
  •  0 \le E \le 10^{5}

考えたこと

「奇数長のサイクルがない」 ⇔ 「二部グラフ」は今となっては典型。

なので、二部グラフである状態を保ちながら辺を付け加えていく問題。最後は完全二部グラフにすることになる。よって、グラフの連結成分ごとに、どちらを左ノードにするかを調節することで、左右のノード数がなるべく均等になるようにする問題だと言える。つまり、各連結成分ごとに、左ノード数と右ノード数との差分と、その -1 倍したもののいずれかを足していき、最終結果をどれだけ 0 に近づけられるかを考える問題となる。

こうして考えてみると、実は ARC 099 E - Independence とまったく同じ問題であることがわかる。ただし、今回は  V \le 10^{5} と制約が大きい。

とりあえず、左ノード数と右ノード数との差分ごとにまとめてみることにする。しかしここでよく考えてみると、左ノード数と右ノード数との差としてありうる値は、最悪  V 通りなのだが、

  • 差が大きすぎるやつは、あんまり多くない (多すぎると  V を超える)
  • 差が小さいやつは、被りまくる可能性がある

という感じ。いい感じに平方分割できる。具体的には

  • 差が  \sqrt{V} 以上のやつはたかだか  O(\sqrt{V}) 種類
  • 差が  \sqrt{V} 以下のやつはそもそも  O(\sqrt{V}) 種類

というわけで、差分ごとにまとめるとありうる値は  O(\sqrt{V}) 種類であることが言える。あとは以下のような個数制限つき重複ナップサック問題を解くことで、解決できる。 O(E + V\sqrt{V})

  • dp[ i ][ v ] := 最初の i 種類だけ見て、総和が v になるようにしたときの、最後の要素の使用最小値
#include <iostream>
#include <vector>
#include <map>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


// nums[i] := i 番目の連結成分の {左ノード数, 右ノード数}, 「dir = 1: 左、-1: 右」
using pint = pair<int,int>;
using Graph = vector<vector<int> >;

bool dfs(const Graph &G, int v, int vdir, pint &num, vector<int> &dir) {
    bool res = true;
    dir[v] = vdir;
    if (vdir == 1) ++num.first;
    else if (vdir == -1) ++num.second;
    for (auto nv : G[v]) {
        if (dir[nv] == 0) {
            if (!dfs(G, nv, -vdir, num, dir)) res = false;
        }
        else if (dir[nv] != -vdir) res = false;
    }
    return res;
}

bool isbipartite(const Graph &G, vector<pint> &nums) {
    bool res = true;
    int N = (int)G.size();
    vector<int> dir(N, 0);
    for (int v = 0; v < N; ++v) {
        if (dir[v] != 0) continue;
        pint num = {0, 0};
        if (!dfs(G, v, 1, num, dir)) res = false;
        nums.push_back(num);
    }
    return res;
}

const int INF = 1<<29;

int main() {
    int V, E; cin >> V >> E;
    Graph G(V);
    for (int i = 0; i < E; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    // 二部グラフ判定して、左ノード数と右ノード数の差分ごとに集計
    vector<pint> nums;
    if (!isbipartite(G, nums)) {
        cout << -1 << endl;
        return 0;
    }
    map<int,int> ma;
    for (auto p : nums) ma[abs(p.first - p.second)]++;
    
    // DP
    int geta = 0;
    vector<int> dp(V*2+10, INF);
    dp[0] = 0;
    for (auto it = ma.begin(); it != ma.end(); ++it) {
        int diff = it->first;
        geta += diff * it->second;
        for (int v = 0; v <= V*2; ++v) {
            if (dp[v] < INF) dp[v] = 0;
        }
        for (int v = 0; v <= V*2; ++v) {
            if (v + diff * 2 <= V*2 && dp[v] < it->second) chmin(dp[v + diff*2], dp[v] + 1);
        }
    }

    // 集計
    int diff = V;
    for (int v = 0; v <= V*2; ++v) {
        if (dp[v] < INF) diff = min(diff, abs(v-geta));
    }
    long long a = (V + diff)/2, b = (V - diff)/2;
    cout << a * b - E << endl;
}