洛谷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;
}