97pts 二分图染色 + dp 求调

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 205;
int n, c[N], m;
bool g[N][N], dp[N][N], vis[N];
vector<int> e[N], id[N][2], ans[2];
PII a[N];
struct node
{
    int x;
    bool f;
}pre[N][N];
bool dfs(int x, int fa, int C)
{
    id[m][C - 1].push_back(x);
    c[x] = C;
    C == 1 ? a[m].x++ : a[m].y++;
    for(int y : e[x])
    {
        if(fa == y)
            continue;
        if(c[y] && c[y] == C)
            return 0;
        else if(c[y])
            continue;
        if(!dfs(y, x, (C == 1 ? 2 : 1)))
            return 0;
    }
    return 1;
}
signed main()
{
    cin >> n;
    for(int i = 1, j; i <= n; i++)
        while(cin >> j && j)
            g[i][j] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(!g[i][j])
                g[j][i] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            if(!g[i][j])
                e[i].push_back(j), e[j].push_back(i);
    for(int i = 1; i <= n; i++)
        if(!c[i])
        {
            m++;
            if(!dfs(i, 0, 1))
                return cout << "No solution", 0;
        }
    // for(int i = 1; i <= m; i++)
    //     cerr << a[i].x << ' ' << a[i].y << endl;
    dp[0][n] = 1;
    for(int i = 1; i <= m; i++)
        for(int j = 0; j <= n << 1ll; j++)
            if(j >= a[i].x && dp[i - 1][j - a[i].x + a[i].y])
                dp[i][j] = 1, pre[i][j] = {j - a[i].x + a[i].y, 0};
            else if(j + a[i].y <= (n << 1ll) && dp[i - 1][j - a[i].y + a[i].x])
                dp[i][j] = 1, pre[i][j] = {j - a[i].y + a[i].x, 1};
    int mini = 1e9, num = 0;
    for(int i = 0; i <= n << 1ll; i += 1)
        if(dp[m][i] && abs(i - n) < mini)
            mini = abs(i - n), num = i;
    int x = num, i = m;
    // cerr << num << endl;
    while(i)
    {
        // cerr << x << endl;
        auto [y, f] = pre[i][x];
        for(int j : id[i][f])
            ans[0].push_back(j);
        for(int j : id[i][!f])
            ans[1].push_back(j);
        vis[i] = f, x = y, i--;
    }
    for(int f = 0; f <= 1; f++)
    {
        cout << ans[f].size() << ' ';
        sort(ans[f].begin(), ans[f].end());
        for(int i : ans[f])
            cout << i << ' ';
        cout << '\n';
    }
    return 0;
}