算法标签：

动态规划 背包 搜索 DFS

题解：

1、只有互相认识的人才能放在同一个组，也就是说前面3中情况都不能放在一个组；

2、在满足前面3中情况的两两之间连线，建立无向图G（可能不是连通图，存在连通分支）；

3、在G中连线的2个人肯定是不能放在同一个分组里面，于是DFS染色，判断G是否是二分图。如果图G不是二分图，那么肯定无解；

如果G是二分图，计算每个连通分支中分成属于x[i]，y[i]2个组的人数（i表示连通分支）；

4、对X，Y 2组人员DP（经典的背包问题)；可以对2个组之间的差值DP范围是（-100~+100），也可以对2个组的人数DP；我选择的是后一种办法。

dp[i]j表示第1组为i个人，第2组为j个人这个状态；dp[i][j]=1表示存在。初始dp[0][0] = 1;然后对每个连通分支DP，转移方程：

if dp[i][j]=1

dp[i+x[k]][j+y[k]] = 1

dp[i+y[k]][j+x[k]] = 1

最后取个差值最小的；

#include <iostream>
#include <cstring>
#include<cmath>
#define inf 1000000
using namespace std;
const int MAXN = 101;
int map[MAXN][MAXN];
int id[2][MAXN];
int color[MAXN];
int dp[MAXN][MAXN];
int tmp[MAXN][MAXN];
struct  
{
    int c1, c2;
    int i, j;
} pre[MAXN][MAXN];
int N, t;

bool DFS(int CurV, int c)
{
    color[CurV] = c;
    id[c % 2][t]++;
    bool ans = true;
    for (int i = 1; i <= N; i++)
    {
        if (map[CurV][i] == 1)
        {
            if (color[i] == -1)
            {
                ans = DFS(i, (c % 2 == 0)? (c + 1) : (c - 1));
                if (ans == false)
                    return false;
            }
            else if (color[i] == color[CurV])
                return false;
        }
    }
    return true;
}

int main()
{
    //freopen("test.txt", "r", stdin);
    cin >> N;
    memset(map, 0, sizeof(map));
    memset(id, 0, sizeof(id));
    memset(color, 0xff, sizeof(color));
    memset(tmp, 0, sizeof(tmp));
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= N; i++)
    {
        int j;
        while (cin >> j && j != 0)
            tmp[i][j] = 1;
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = i + 1; j <= N; j++)
        {
            if (!(tmp[i][j] == 1 && tmp[j][i] == 1))
                map[i][j] = map[j][i] = 1;
        }
    }
    bool ans;
    int c = 0;
    t = 0;
    for (int i = 1; i <= N; i++)
    {
        if (color[i] == -1)
        {
            ans = DFS(i, c);
            c += 2;
            t++;
            if (ans == false)
                break;
        }
    }
    if (ans == false)
        cout << "No solution" << endl;
    else
    {
        int n = 0;
        dp[0][0] = 1;
        for (int k = 0; k < t; k++)
        {
            for (int i = 0; i <= n; i++)
            {
                int j = n - i;
                if (dp[i + id[0][k]][j + id[1][k]] == 0 && dp[i][j] == 1)
                {
                    pre[i + id[0][k]][j + id[1][k]].c1 = k * 2;
                    pre[i + id[0][k]][j + id[1][k]].c2 = k * 2 + 1;
                    pre[i + id[0][k]][j + id[1][k]].i = i;
                    pre[i + id[0][k]][j + id[1][k]].j = j;
                    dp[i + id[0][k]][j + id[1][k]] = 1;
                }
                if (dp[i + id[1][k]][j + id[0][k]] == 0 && dp[i][j] == 1)
                {
                    pre[i + id[1][k]][j + id[0][k]].c1 = k * 2 + 1; // 记录颜色
                    pre[i + id[1][k]][j + id[0][k]].c2 = k * 2; // 记录颜色
                    pre[i + id[1][k]][j + id[0][k]].i = i;
                    pre[i + id[1][k]][j + id[0][k]].j = j;
                    dp[i + id[1][k]][j + id[0][k]] = 1;
                }
            }
            n += id[0][k] + id[1][k];
        }
        int res = inf;
        int a, b;
        for (int i = 1; i <= N; i++)
        {
            int j = N - i;
            if (dp[i][j] == 1 && res > abs(i - j))
            {
                a = i;
                b = j;
                res = abs(i - j);
            }
        }
        cout << a;
        for (int i = a, j = b; !(i == 0 && j == 0);)
        {
            int c = pre[i][j].c1;
            for (int k = 1; k <= N; k++)
            {
                if (color[k] == c)
                    cout << " " << k;
            }
            int _i = i;
            i = pre[i][j].i;
            j = pre[_i][j].j;
        }
        cout << endl;
        cout << b;
        for (int i = a, j = b; !(i == 0 && j == 0);)
        {
            int c = pre[i][j].c2;
            for (int k = 1; k <= N; k++)
            {
                if (color[k] == c)
                    cout << " " << k;
            }
            int _i = i;
            i = pre[i][j].i;
            j = pre[_i][j].j;
        }
        cout << endl;
    }
    return 0;
}