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個(gè)人分成2各組，每一個(gè)人有他所認(rèn)識(shí)的人。所分的組有四點(diǎn)要求：

1、 每個(gè)人都必需屬于一個(gè)組。

2、 每個(gè)組至少有一個(gè)人。

3、 每個(gè)組里面的每個(gè)人必需互相認(rèn)識(shí)。

4、 兩個(gè)組的成員應(yīng)盡量接近。

首先分析這道題目，題目給出的是一個(gè)有向圖，即如果有A認(rèn)識(shí)B，但不一定有B認(rèn)識(shí)A。但是在所分配的組里面，任意兩個(gè)人都要互相認(rèn)識(shí)。

1、 先讀入數(shù)據(jù)建立有向圖，然后對(duì)這個(gè)有向圖進(jìn)行處理，如果兩個(gè)點(diǎn)之間的邊是單向邊，就認(rèn)為兩個(gè)點(diǎn)之間無(wú)邊（因?yàn)檫@兩個(gè)人不互相認(rèn)識(shí)），對(duì)于兩個(gè)點(diǎn)間的雙向邊，即建立一條無(wú)向邊（這兩個(gè)人互相認(rèn)識(shí)），這樣就可以把一個(gè)有向圖轉(zhuǎn)化為一個(gè)無(wú)向圖。

2、 將這個(gè)無(wú)向圖轉(zhuǎn)化為它的反圖。即有邊的把邊刪去，無(wú)邊的添上一條邊。（其實(shí)1，2步在程序?qū)崿F(xiàn)時(shí)可以一次完成）。

3、 對(duì)轉(zhuǎn)換后的反圖求極大連通分量。想想就會(huì)明白剛才為什么要求反圖，可以看到在這個(gè)反圖中的不同的連通分量中的兩個(gè)人都是互相認(rèn)識(shí)的！！！接下來(lái)很關(guān)鍵，那些互不認(rèn)識(shí)的人就在一個(gè)連通分量里面。

4、 在做DFS求連通分量的時(shí)候，同時(shí)對(duì)連通分量中的點(diǎn)染色（0或1），如果一個(gè)點(diǎn)顏色為0，那么所有和它相鄰的點(diǎn)與它的顏色應(yīng)該不同（標(biāo)記為1）。這是因?yàn)榉磮D中相鄰的兩個(gè)人都是不認(rèn)識(shí)的（回顧剛才反圖的作用）。這樣DFS結(jié)束后，就可以根據(jù)顏色把連通分量中的點(diǎn)分成兩個(gè)組s0和s1，在不同兩個(gè)組的人是不可能分到一個(gè)team內(nèi)的。到這里要做一個(gè)特判，對(duì)于s0或s1組里的任意兩個(gè)人p,q如果反圖中存在一條邊(p,q)，說(shuō)明無(wú)解，輸出"No solution"。

5、 求出了所有的連通分量，對(duì)于第i個(gè)連通分量都把其節(jié)點(diǎn)分為兩個(gè)組s1i和s2i。這時(shí)要做的就是把所有的s1i和s2i分配到team1和team2中去，使team1的總和與team2的總和差值最小。就可以用背包DP了。
dp[i][j]表示第i個(gè)連通分量達(dá)到j的差值，true為可達(dá)，false為不可達(dá)。
狀態(tài)轉(zhuǎn)移方程：
dp[i][j+si0-si1]=true if dp[i-1][j] == true
dp[i][j-si0+si1]=true if dp[i-1][j] == true
同時(shí)記錄轉(zhuǎn)移路徑，差值j的范圍是-100~+100可以坐標(biāo)平移。
最后在dp[m][i]（m是最后一個(gè)連通塊數(shù)）中找出值為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