洛谷P1285 队员分组题解

题意：

有 \(n\) 个人从 \(1\) 至 \(n\) 编号，相互之间有一些认识关系，你的任务是把这些人分成两组，使得：

每个人都被分到其中一组。

每个组都至少有一个人。

一组中的每个人都认识其他同组成员。

在满足上述条件的基础上，要求两组成员的人数之差（绝对值）尽可能小。请构造一种可行的方案。

请注意，\(x\) 认识 \(y\) 不一定说明 \(y\) 认识 \(x\)；\(x\) 认识 \(y\) 且 \(y\) 认识 \(z\) 不一定说明 \(x\) 认识 \(z\)。即认识关系是单向且不可传递的。

输入格式：

输入的第一行是一个整数，代表总人数 \(n\)。

第 \(2\) 到第 \((n + 1)\) 行，每行有若干个互不相同的整数，以 \(0\) 结尾，第 \((i + 1)\) 行的第 \(j\) 个整数 \(a_{i, j}\)（\(0\) 除外）代表第 \(i\) 个人认识 \(a_{i, j}\)。

输出格式：

本题存在 Special Judge。

如果无解，请输出一行一个字符串 No solution。

如果有解，请输出两行整数，分别代表两组的成员。每行的第一个整数是该组的人数，后面以升序若干个整数代表该组的成员编号，数字间用空格隔开。

数据范围：

保证 \(2 \leq n \leq 100\)，\(1 \leq a_{i, j} \leq n\)。

考虑建立原图关于 \(n\) 阶完全图的补图，然后把补图的边全部改成无向边。

这样每条边 \((u,v)\) 就意味着 \(u,v\) 必须分到不同的集合内。

考虑设 \(f(i,j)\) 为前 \(i\) 个连通块能否达到 \(0/1\) 的大小，那么显然 \[ f(i,j) = f(i - 1,\, j - \mathrm{size}(i,0)) \lor f(i - 1,\, j - \mathrm{size}(i,1)) \] 显然答案要求最大的 \(j~(1 \le j \le \frac{n}{2})\) 满足 \(f(k, j) = \mathrm{True}\) ，

其中 \(k\) 表示连通块的总个数，这样可以保证差的绝对值尽可能小。

时间复杂度 \(\mathcal{O}(n^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define N ((int)(114))

bitset<N> used, g[N], dp[N], type[N];
int n, cnt, ans, col[N], res[N];
vector<int> vec[N][2];
void dfs(int u, int fa, int c)
{
    vec[cnt][col[u] = c].pb(u);
    rep(v, 1, n) if(v != u && v != fa && !g[v][u])
    {
        if(!(~col[v])) dfs(v, u, c ^ 1);
        else if(col[v] == c) { cout << "No solution\n"; exit(0); }
    }
}
void solve()
{
    dp[0][0] = true;
    rep(i, 1, cnt) rep(j, 0, n / 2)
    {
        int t = j - vec[i][0].size();
        if(t >= 0 && dp[i - 1][t]) { dp[i][j] = true, type[i][j] = 0; }
        t = j - vec[i][1].size();
        if(t >= 0 && dp[i - 1][t]) { dp[i][j] = true; type[i][j] = 1; }
    }
    Rep(i, n / 2, 0) if(dp[cnt][i]) { ans = i; break; }
}
void output()
{
    int t = ans; 
    Rep(i, cnt, 1)
    {
        for(auto j : vec[i][type[i][t]])
            used[res[++res[0]] = j] = true;
        t -= vec[i][type[i][t]].size();
    }
    sort(res + 1, res + 1 + res[0]);
    cout << res[0] << ' ';
    rep(i, 1, res[0]) cout << res[i] << " \n"[i == res[0]];
    cout << n - res[0] << ' '; t = 0;
    rep(i, 1, n) if(!used[i]) cout << i << " \n"[++t == n - res[0]];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int x; cin >> n;
    rep(i, 1, n) while(cin >> x && x) g[i][x] = true;
    rep(i, 1, n) rep(j, i + 1, n)
        if(!g[i][j] || !g[j][i]) { g[i][j] = g[j][i] = false; }
    memset(col, -1, sizeof(col));
    rep(i, 1, n) if(!(~col[i])) { ++cnt, dfs(i, 0, 1); }
    solve(); output();
    return 0;
}