【精進】ARC099 E - Independence

補グラフ、２部グラフ、DP

問題概要

E - Independence
$N$頂点$M$辺の無向グラフがある。グラフを2つの完全グラフに分けることができるかを判定し、できるなら両グラフの辺の数の和の最小値を求めよ。

解法

補グラフを考える。頂点を$S,T=[N]\setminus S$に分けるとき、辺は$S,T$間にのみ張られている必要がある。従って補グラフが2部グラフでないなら不可能である。連結成分ごとに考える。連結な2部グラフは一意に2つの互いに隣接しない頂点集合に分けることができ、一方が$S$,他方が$T$に含まれる。各連結成分のそのような頂点集合のサイズを$x_i,y_i$とすると求めるのは

\[\begin{align*} \text{minimize}\quad &\frac{|S| (|S|-1)}{2}+\frac{|T| (|T|-1)}{2} \\ \text{subject to}\quad & |S| = \sum_i z_i \\ & |T| = N - |S| \\ & z_i \in \{x_i,y_i\} \end{align*}\]

になる。 そのためには$|S|$としてあり得るものを列挙できればよいが、連結成分の個数も$|S|$も$N$以下なのでDPを用いて計算できる。

#include "template.hpp"
pair<Graph, ll> make_g() {
    LL(n, m);
    vector _g(n, vector<bool>(n, true));
    rep(i, m) {
        LL(a, b);
        _g[--a][--b] = false;
        _g[b][a] = false;
    }
    Graph g(n);
    rep(i, n) rep(j, n) if(i != j and _g[i][j]) g[i].push_back(j);
    return {g, n * (n - 1) / 2 - m};
}
void solve() {
    auto [g, m] = make_g();
    ll n = g.size();
    vl used(n, -1);
    vl zo(2);
    queue<ll> q;
    vector<vector<ll>> add_sz;
    rep(i, n) {
        zo[0] = zo[1] = 0;
        if(used[i] != -1)
            continue;
        zo[0]++;
        used[i] = 0;
        q.push(i);
        while(q.size()) {
            ll now = q.front();
            q.pop();
            for(auto nex : g[now]) {
                if(used[nex] == used[now]) {
                    // ２部グラフでない
                    print(-1);
                    return;
                }
                if(used[nex] == -1) {
                    used[nex] = 1 ^ used[now];
                    zo[used[nex]]++;
                    q.push(nex);
                }
            }
        }
        add_sz.push_back(zo);
    }
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for(auto v : add_sz) {
        auto prev = dp;
        fill(all(dp), false);
        rep(i, n + 1) {
            if(prev[i])
                rep(j, 2) if(i + v[j] <= n) {
                    dp[i + v[j]] = true;
                }
        }
    }
    ll ans = inf;
    rep(i, n + 1) {
        if(dp[i]) {
            chmin(ans, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
        }
    }
    print(ans);
}
int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
}