学步园

这道题目我一点思路都没有，不会做呀。。。。

看了http://www.cppblog.com/linyangfei/archive/2008/08/08/58295.html

http://happylch21.blog.163.com/blog/static/165639759201162911032307/

这两位大牛的，把他们两的结合起来~~

题目的大意就是：

把n个人分成2各组，每一个人有他所认识的人。所分的组有四点要求：

1、 每个人都必需属于一个组。

2、 每个组至少有一个人。

3、 每个组里面的每个人必需互相认识。

4、 两个组的成员应尽量接近。

思路：建立图，若i关注了j,j也关注了i则i与j建立一条双向边~，然后求这个图的补图，那么补图中的边连的两个点必然不能在一个组中是两个互斥的点，这样分成两个组，这样就转化成2分染色问题，深度遍历进行染色，若染色过程中，发现同组有相邻点，则表示无解。求出每组中包含了多少个结点和每组包含了哪些结点

num[i][0]表示第i个强连通分量里颜色为0的个数，num[i][1]表示第i个强连通分量里颜色为1的个数。

p[i][0][k]表示第i个连通分量里颜色为0的第k个点是哪个结点,同理p[i][1][k]表示第i个连通分量里颜色为1的第k个点是哪个结点。

然后转换为0/1背包问题

dp[i][j]表示前i对数能否将容量j填满

dp[i][j] = dp[i][j - num[i][0]] ;    j > num[i][0]

dp[i][j] = dp[i][j - num[i][1]];     j > num[i][1]

同时记录路径

dp[i][n/2]即为最终的结果

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 110;

bool graph[maxn][maxn], dp[maxn][maxn/2];
int n, cnt, p[maxn][2][maxn], num[maxn][2], color[maxn], path[maxn][maxn];

bool dfs(int u);
void compute();

int main()
{
    scanf("%d", &n);
    memset(graph, 0, sizeof(graph));
    memset(num, 0, sizeof(num));
    memset(color, -1, sizeof(color));
    for(int i = 1; i <= n; i++)
    {
        while(true)
        {
            int index;
            scanf("%d", &index);
            if(index == 0)
                break;
            graph[i][index] = true;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
           if(graph[i][j] && graph[j][i])
                graph[i][j] = graph[j][i] = false;
            else
                graph[i][j] = graph[j][i] = true;
        }
    }
    cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        if(color[i] == -1)
        {
            color[i] = 0;
            if(!dfs(i))
            {
                printf("No solution\n");
                return 0;
            }
            cnt++;
        }
    }
    compute();
   
    return 0;
}

bool dfs(int u)
{
    int col = color[u];
    int index = num[cnt][col];
    num[cnt][col]++;
    p[cnt][col][index] = u;
    for(int i = 1; i <= n; i++)
    {
        if(graph[u][i])
        {
            if(color[i] == -1)
            {
                color[i] = col ^ 1;
                if(!dfs(i))
                    return false;
            }
            else if(color[u] == color[i])
                return false;
        }
        
    }
    return true;
}



void compute()
{
    int i, j, k, tmp, res, col;
    memset(dp, 0, sizeof(dp));
    dp[0][num[0][0]] = true;
    path[0][num[0][0]] = 0;
    dp[0][num[0][1]] = true;
    path[0][num[0][1]] = 1;
    
    for(i = 1; i < cnt; i++)
    {
        for(j = n / 2; j >= 0; j--)
        {
            dp[i & 1][j] = false;
            tmp = j - num[i][0];
            if(tmp >= 0 && dp[(i-1) & 1][tmp])
            {
                dp[i & 1][j] = true;
                path[i][j] = 0;
                if(i == cnt - 1)
                    break;
                continue;
            }
            tmp = j - num[i][1];
            if(tmp >= 0 && dp[(i-1) & 1][tmp])
            {
                dp[i & 1][j] = true;
                path[i][j] = 1;
                if(i == cnt - 1)
                    break;
            }
        }
    }
    
    tmp = j;
    res = 0;
    for(i = cnt - 1; i >= 0; i--)
    {
        if(path[i][j] == 0)
        {
            res += num[i][0];
            j -= num[i][0];
        }
        else
        {
            res += num[i][1];
            j -= num[i][1];
        }
    }
    printf("%d", res);
    j = tmp;
    for(i = cnt - 1; i >= 0; i--)
    {
        col = 1;
        if(path[i][j] == 0)
        {
            col = 0;
            j -= num[i][0];
        }
        else
            j -= num[i][1];
        for(k = 0; k < num[i][col]; k++)
            printf(" %d", p[i][col][k]);
    }
    printf("\n%d", n - res);
    j = tmp;
    for(i = cnt - 1; i >= 0; i--)
    {
        col = 0;
        if(path[i][j] == 0)
        {
            col = 1;
            j -= num[i][0];
        }
        else
            j -= num[i][1];
        for(k = 0; k < num[i][col]; k++)
            printf(" %d", p[i][col][k]);
    }
    printf("\n");
}