P1285 题解

· · 题解

二分图染色+背包。

首先看到分成两组，想到二分图。如果两个人不是互相认识的话则不能在同一个组，这启发我们按照排斥关系建边，注意如果两个人不是互相认识，就算有一个人认识另一个人，也需要建边（双向边）。

然后我们对于这个图进行二分图染色，在一个连通块内，染出两种颜色，构造方案就变成了把每个连通块中两种颜色的点分别放入要求的两组中，并且使得两组的人数差尽量地小。不难发现这是一个背包问题。设计状态 dp_{i, j} 表示在前 i 个连通块中，第 1 组的总人数为 j 的是否可行。转移是简单的，对于第 i 个连通块，讨论是选择颜色为 1 或 2 的人放入第 1 组。所以在染色的时候同时需要维护每个点被染上的颜色 col_i，所属的连通块 blk_i，每个连通块颜色为 1 或 2 的点数量 sz_{i, 1/2}，方便转移和方案输出。

题目还要求输出方案，于是设 p_{i, j} 表示状态 dp_{i, j} 中，第 i 个连通块选择了颜色为 i 的点放入第 1 组。然后直接递归转移即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105;
int n, sz[N][3], p[N][N], col[N], blk[N], cnt, tot1, tot2, p1[N], p2[N]; //sz[i][j] 表示在第 i 个块中，颜色为 j 的点数量
bool ed[N][N], dp[N][N]; //dp[i][j] 表示前i个联通块，第一组的点数量为j时，是否可行 
vector <int> G[N];

bool coloring(int u, int c, int b) {
    col[u] = c; sz[b][c]++; blk[u] = b;
    for (int v : G[u]) {
        if(col[v] == c) return 0;
        else if(!col[v]) {
            if(!coloring(v, 3 - c, b)) return 0;
        }
    }
    return 1;
} 

void divideg(int cur, int x) {
    if(cur == 0) return ;
    if(p[cur][x] == 1) {
        for (int i = 1; i <= n; ++i) {
            if(blk[i] == cur) {
                if(col[i] == 1) p1[++tot1] = i;
                else p2[++tot2] = i;
            }
        }
        divideg(cur - 1, x - sz[cur][1]);
    }
    else {
        for (int i = 1; i <= n; ++i) {
            if(blk[i] == cur) {
                if(col[i] == 2) p1[++tot1] = i;
                else p2[++tot2] = i;
            }
        }
        divideg(cur - 1, x - sz[cur][2]);
    }
    return ;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int a;
        while(scanf("%d", &a)) {
            if(a == 0) break;
            ed[i][a] = 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if(!ed[i][j] || !ed[j][i]) G[i].emplace_back(j), G[j].emplace_back(i);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if(!col[i]) {
            if(!coloring(i, 1, ++cnt)) return puts("No solution"), 0;
        }
    }
    dp[0][0] = 1;
    for (int i = 1; i <= cnt; ++i) {
        for (int j = 0; j <= n; ++j) { //目前一共有 j 个颜色为 1 的点
            //若第i个联通块选择了颜色为1的点
            int k = j - sz[i][1];
            if(k >= 0) {
                if(dp[i - 1][k]) dp[i][j] = 1, p[i][j] = 1; //p[i][j] 指状态 dp[i][j] 是在第 i 个连通块中选择了颜色为 p[i][j] 的转移过来的
            }
            k = j - sz[i][2];
            //若第i个联通块选择了颜色为2的点
            if(k >= 0) {
                if(dp[i - 1][k]) dp[i][j] = 1, p[i][j] = 2;
            }
        }
    }
    int ans = 114514, pos;
    for (int i = 0; i <= n; ++i) if(dp[cnt][i] && abs(n - 2 * i) < ans) ans = abs(n - 2 * i), pos = i;
    if(ans == 114514) return puts("No solution"), 0;
    // cout << pos << "\n";
    divideg(cnt, pos);
    sort(p1 + 1, p1 + tot1 + 1);
    sort(p2 + 1, p2 + tot2 + 1);
    printf("%d ", tot1);
    for (int i = 1; i <= tot1; ++i) printf("%d ", p1[i]);
    puts("");
    printf("%d ", tot2);
    for (int i = 1; i <= tot2; ++i) printf("%d ", p2[i]);
    puts("");
    return 0;
}