AtCoder ARC 099 E - Independence (黄色, 700 点)

いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たい。

類題として

• AOJ 2370 RabbitWalking　(二部グラフ判定からの部分和ナップサックが酷似)
• POJ 3692 Kindergarten　(補グラフとって二部グラフにする発想)

があるのん。これらを経験しておくと、この問題は確かに典型だと思えるのん。

• 問題へのリンク

問題概要

N 頂点 M 辺の無向単純グラフが与えられる。全頂点を「白」と「黒」に塗り分ける。

白からなる部分グラフもクリークをなし、黒からなる部分グラフもクリークをなすような色塗り方法のうち、各クリークに含まれる辺数の総和が最小になるようなものを求めよ。(塗り分け不可能な場合は -1)

制約

• 

解法

2 つのクリークにわける方法についての問題。クリークと言われると補グラフをとりたくなる。補グラフをとると、

• クリーク
• 安定集合 (独立集合)

は互いに移り合う。今回は 2 つのクリークにわける問題であるが、補グラフをとった世界では

---

二部グラフにわけて (左右をそれぞれ白と黒に塗る)、左側頂点数を L、右側頂点数を R としたときに L(L-1)/2 + R(R-1)/2 を最小にせよ

---

という問題になる。L + R = N であって、L として取り得る値がわかっているならこの最適化は簡単で、L と R がなるべく均等になるようにするとよい。具体的には、L が N/2 に最も近くなるようにすればよい。

つまり、補グラフの各連結成分ごとに二部グラフにして左 / 右のノード数が (a[i], b[i]) であれば、各連結成分ごとに a か b かを選択していってその和がなるべく N/2 に近くなるようにする問題になる。これは部分和問題とほとんど一緒であり、ナップサック DP で求められる。

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 2100;
bool G[MAX][MAX];
int N, M;

bool isbipartite = true; // false になったら二部グラフでない
int dir[MAX]; // 各ノードをとりあえず左右どちらにしているか (左: 0、右: 1)
int tmpnums[2];

void dfs(int v, int tdir) {
    dir[v] = tdir;
    tmpnums[tdir]++;
    for (int e = 0; e < N; ++e) {
        if (e == v || !G[v][e]) continue;
        if (dir[e] == -1) dfs(e, 1 - tdir);
        else if (dir[e] != 1 - tdir) isbipartite = false;
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < MAX; ++i) for (int j = 0; j < MAX; ++j) G[i][j] = 1;
    for (int i = 0; i < M; ++i) {
      int a, b;
      cin >> a >> b; --a, --b;
      G[a][b] = G[b][a] = 0;
    }
    
    // 二部グラフの構成
    vector<pair<int,int> > nums;
    for (int i = 0; i < MAX; ++i) dir[i] = -1;
    for (int v = 0; v < N; ++v) {
        if (dir[v] != -1) continue;
        tmpnums[0] = tmpnums[1] = 0;
        dfs(v, 0);
        nums.push_back(make_pair(tmpnums[0], tmpnums[1]));
    }

    // そもそも二部グラフじゃなかったらダメ
    if (!isbipartite) {
        cout << -1 << endl;
        return 0;
    }

    // ナップサック DP
    bool dp[MAX] = {0};
    dp[0] = 1;
    for (int i = 0; i < (int)nums.size(); ++i) {
        for (int j = N; j >= 0; --j) {
            if (!dp[j]) continue;
            dp[j] = 0;
            dp[j + nums[i].first] = 1;
            dp[j + nums[i].second] = 1;
        }
    }

    long long a = -1;
    long long mindif = N;
    for (int i = 0; i <= N; ++i) {
        if (!dp[i]) continue;
        if (mindif > abs(i - N/2)) mindif = abs(i - N/2), a = i;
    }
    long long b = N-a;
    cout << a*(a-1)/2 + b*(b-1)/2 << endl;
}