Team Them Up!

Description

Your task is to divide a number of persons into two teams, in such a way, that:

everyone belongs to one of the teams;

every team has at least one member;

every person in the team knows every other person in his team;

teams are as close in their sizes as possible.

This task may have many solutions. You are to find and output any solution, or to report that the solution does not exist.

Input

For simplicity, all persons are assigned a unique integer identifier from 1 to N.

The first line in the input file contains a single integer number N (2 <= N <= 100) - the total number of persons to divide into teams, followed by N lines - one line per person in ascending order of their identifiers. Each line contains the list of distinct numbers Aij (1 <= Aij <= N, Aij != i) separated by spaces. The list represents identifiers of persons that ith person knows. The list is terminated by 0.

Output

If the solution to the problem does not exist, then write a single message "No solution" (without quotes) to the output file. Otherwise write a solution on two lines. On the first line of the output file write the number of persons in the first team, followed by the identifiers of persons in the first team, placing one space before each identifier. On the second line describe the second team in the same way. You may write teams and identifiers of persons in a team in any order.

Sample Input

5

2 3 5 0

1 4 5 3 0

1 2 5 0

1 2 3 0

4 3 2 1 0

Sample Output

3 1 3 5

2 2 4

Source

Northeastern Europe 2001

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

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

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

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

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

首先分析这道题目，题目给出的是一个有向图，即如果有A认识B，但不一定有B认识A。但是在所分配的组里面，任意两个人都要互相认识。

1、 先读入数据建立有向图，然后对这个有向图进行处理，如果两个点之间的边是单向边，就认为两个点之间无边（因为这两个人不互相认识），对于两个点间的双向边，即建立一条无向边（这两个人互相认识），这样就可以把一个有向图转化为一个无向图。

2、 将这个无向图转化为它的反图。即有边的把边删去，无边的添上一条边。（其实1，2步在程序实现时可以一次完成）。

3、 对转换后的反图求极大连通分量。想想就会明白刚才为什么要求反图，可以看到在这个反图中的不同的连通分量中的两个人都是互相认识的！！！接下来很关键，那些互不认识的人就在一个连通分量里面。

4、 在做DFS求连通分量的时候，同时对连通分量中的点染色（0或1），如果一个点颜色为0，那么所有和它相邻的点与它的颜色应该不同（标记为1）。这是因为反图中相邻的两个人都是不认识的（回顾刚才反图的作用）。这样DFS结束后，就可以根据颜色把连通分量中的点分成两个组s0和s1，在不同两个组的人是不可能分到一个team内的。到这里要做一个特判，对于s0或s1组里的任意两个人p,q如果反图中存在一条边(p,q)，说明无解，输出"No solution"。

5、 求出了所有的连通分量，对于第i个连通分量都把其节点分为两个组s1i和s2i。这时要做的就是把所有的s1i和s2i分配到team1和team2中去，使team1的总和与team2的总和差值最小。就可以用背包DP了。
dp[i][j]表示第i个连通分量达到j的差值，true为可达，false为不可达。
状态转移方程：
dp[i][j+si0-si1]=true if dp[i-1][j] == true
dp[i][j-si0+si1]=true if dp[i-1][j] == true
同时记录转移路径，差值j的范围是-100~+100可以坐标平移。
最后在dp[m][i]（m是最后一个连通块数）中找出值为true的最小i值。输出答案。

  1#include <stdio.h>
  2#include <string.h>
  3
  4int g[205][205],r[205][205],n;
  5int mark[205],cnt,dp[205][205];
  6char st[205][205][105];
  7struct P
  8{
  9    int a[2];
 10    int s[2][105];
 11}p[105];
 12
 13void dfs(int v, int color, int num)
 14{
 15    int i;
 16    mark[v]=true;
 17    p[num].s[color][p[num].a[color]]=v;
 18    p[num].a[color]++;
 19    for(i=1; i<=n; i++)
 20    {
 21        if(!mark[i] && r[v][i])
 22        {
 23            dfs(i,color^1,num);
 24        }
 25    }
 26}
 27bool fit()
 28{
 29    int i,j,k;
 30    for(i=0; i<cnt; i++)
 31    {
 32        for(j=0; j<p[i].a[0]; j++)
 33        {
 34            for(k=j+1; k<p[i].a[0]; k++)
 35            {
 36                if(r[p[i].s[0][j]][p[i].s[0][k]])
 37                    return false;
 38            }
 39        }
 40        for(j=0; j<p[i].a[1]; j++)
 41        {
 42            for(k=j+1; k<p[i].a[1]; k++)
 43            {
 44                if(r[p[i].s[1][j]][p[i].s[1][k]])
 45                    return false;
 46            }
 47        }
 48    }
 49    return true;
 50}
 51
 52int main()
 53{
 54    int i,j,k,ii,t,flag,ans1[105],ans2[105];
 55    //freopen("in.txt","r",stdin);
 56    scanf("%d",&n);
 57    memset(g,0,sizeof(g));
 58    memset(r,0,sizeof(r));
 59    for(i=1; i<=n; i++)
 60    {
 61        while(scanf("%d",&j), j)
 62        {
 63            g[i][j]=1;
 64        }
 65    }
 66    for(i=1; i<=n; i++)
 67    {
 68        for(j=1; j<=n; j++)
 69        {
 70            if(!g[i][j] || !g[j][i])
 71                r[i][j]=r[j][i]=1;
 72        }
 73    }
 74    memset(mark,0,sizeof(mark));
 75    cnt=0;
 76    memset(p,0,sizeof(p));
 77    for(i=1; i<=n; i++)
 78    {
 79        if(!mark[i])
 80        {
 81            dfs(i,0,cnt++);
 82        }
 83    }
 84    if(!fit())
 85    {
 86        printf("No solution\n");
 87        return 0;
 88    }
 89    memset(dp,0,sizeof(dp));
 90    memset(st,0,sizeof(st));
 91    dp[0][100+p[0].a[0]-p[0].a[1]]=1;
 92    memset(st[0][100+p[0].a[0]-p[0].a[1]],0,sizeof(st[0][100+p[0].a[0]-p[0].a[1]]));
 93    for(i=0; i<p[0].a[0]; i++)
 94        st[0][100+p[0].a[0]-p[0].a[1]][p[0].s[0][i]]=1;
 95    dp[0][100-p[0].a[0]+p[0].a[1]]=1;
 96    memset(st[0][100-p[0].a[0]+p[0].a[1]],0,sizeof(st[0][100-p[0].a[0]+p[0].a[1]]));
 97    for(i=0; i<p[0].a[1]; i++)
 98        st[0][100-p[0].a[0]+p[0].a[1]][p[0].s[1][i]]=1;
 99    for(i=1; i<cnt; i++)
100    {
101        for(j=100+n; j>=100-n; j--)
102        {
103            if(dp[i-1][j])
104            {
105                //for(k=0; k<cnt; k++)
106                //{
107                    t=j+p[i].a[0]-p[i].a[1];
108                    if(!dp[i][t])
109                    {
110                        dp[i][t]=1;
111                        memcpy(st[i][t],st[i-1][j],sizeof(st[i-1][j]));
112                        for(ii=0; ii<p[i].a[0]; ii++)
113                            st[i][t][p[i].s[0][ii]]=1;
114                        
115                    }
116                    t=j-p[i].a[0]+p[i].a[1];
117                    if(!dp[i][t])
118                    {
119                        dp[i][t]=1;
120                        memcpy(st[i][t],st[i-1][j],sizeof(st[i-1][j]));
121                        for(ii=0; ii<p[i].a[1]; ii++)
122                        {
123                            st[i][t][p[i].s[1][ii]]=1;
124                        }
125                    }
126                //}
127            }
128        }
129    }
130    flag=0;
131    for(i=0; i<n; i++)
132    {
133        if(dp[cnt-1][100+i])
134        {
135            t=0;
136            k=0;
137            for(j=1; j<=n; j++)
138            {
139                if(st[cnt-1][100+i][j])
140                {
141                    ans1[t++]=j;
142                }
143                else
144                    ans2[k++]=j;
145            }
146            if(t && k)
147            {
148                flag=1;
149                printf("%d",t);
150                for(j=0; j<t; j++)
151                    printf(" %d",ans1[j]);
152                printf("\n");
153                printf("%d",k);
154                for(j=0; j<k; j++)
155                    printf(" %d",ans2[j]);
156                printf("\n");
157                break;
158            }
159        }
160        if(dp[cnt-1][100-i])
161        {
162            t=0;
163            k=0;
164            for(j=1; j<=n; j++)
165            {
166                if(st[cnt-1][100-i][j])
167                {
168                    ans1[t++]=j;
169                }
170                else
171                    ans2[k++]=j;
172            }
173            if(t && k)
174            {
175                flag=1;
176                printf("%d",t);
177                for(j=0; j<t; j++)
178                    printf(" %d",ans1[j]);
179                printf("\n");
180                printf("%d",k);
181                for(j=0; j<k; j++)
182                    printf(" %d",ans2[j]);
183                printf("\n");
184                break;
185            }
186        }
187    }
188    if(!flag)
189        printf("No solution\n");
190    return 0;
191}
192
193