ARC099 E Independence

問題文

https://beta.atcoder.jp/contests/arc099/tasks/arc099_c

 

グラフの各頂点を赤/青の2色でぬるとき,両端点の色が等しい辺の数の最小値を求める問題.ただし同じ色でぬられた頂点はそれぞれクリークになっていないといけない.

Wikipediaに「元のグラフのクリークは補グラフの独立集合と対応する」と書いてあるのがヒントになった.

元のグラフの頂点を2つのクリークに分割するということは,補グラフで2つの独立集合に分割することに等しい.このような分割が出来るとき,そのグラフは二部グラフと呼ばれる.よって,このような分割が出来るかは二部グラフ判定で出来る.

二部グラフならば,補グラフの各連結成分について,そのグラフの2-彩色方法は色の入れ替えを無視して一意に定まる.

ここで,両端点の色が等しい辺の数は,クリーク(独立集合)の頂点数だけで決まることに注目すると,各連結成分を2つに分割してどちらか一方を選んでいったときに出来るクリークの頂点数をDPで列挙し,あり得るものを全て試せば最小値が求まることがわかる.

 

「最大クリーク問題(最大独立問題)」はNP困難で,「最小クリーク被覆問題」はNP完全であるなど,クリークに関する問題は難しそうだが,2つのクリークに分割するときは二部グラフになって簡単になるのが面白い.

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
vector<int> G[700];
bool is_c[700][700];
bool dp[2][701];
int color[700];
bool vis[700];
bool dfs(int v, int c) {
    color[v] = c;
    vis[v] = 1;
    for (int to : G[v]) {
        if (color[to] == c) return 0;
        if (!color[to] && !dfs(to, -c)) return 0;
    }
    return 1;
}
int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        is_c[a][b] = is_c[b][a] = 1;
    }
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (is_c[i][j]) continue;
            G[i].push_back(j);
            G[j].push_back(i);
        }
    }
    int k = 0;
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        if (vis[i]) continue;
        memset(color, 0, sizeof(color));
        if (!dfs(i, 1)) {
            cout << -1 << endl;
            return 0;
        }
        int s = 0, t = 0;
        for (int j = 0; j < N; j++) {
            if (color[j] == 1) s++; else if (color[j] == -1) t++;
        }
        for (int j = 0; j + s <= N; j++) {
            if (!dp[k & 1][j]) continue;
            dp[(k + 1) & 1][j + s] = 1;
        }
        for (int j = 0; j + t <= N; j++) {
            if (!dp[k & 1][j]) continue;
            dp[(k + 1) & 1][j + t] = 1;
        }
        for (int j = 0; j <= N; j++) dp[k & 1][j] = 0;
        k++;
    }
    int ans = 1 << 30;
    for (int i = 0; i <= N; i++) {
        if (!dp[k & 1][i]) continue;
        ans = min(ans, i*(i - 1) / 2 + (N - i)*(N - i - 1) / 2);
    }
    cout << ans << endl;
}