強(qiáng)烈推薦此題。圖論和DP結(jié)合。
首先，我們分析一下分組的要求：
1、把所有的人分成2組，每組至少有1人；
2、每組之間的人兩兩認(rèn)識。
非常明顯，如果存在兩個(gè)人A和B，A不認(rèn)識B，或B不認(rèn)識A，那么A和B一定不能分在同一組。因此，我們以人為結(jié)點(diǎn)重新構(gòu)造一個(gè)圖G。假如A和B不能分在同一組，那么就在G中增加一條無向邊(A,B)。這樣，我們就得到了一個(gè)較為“單純”的模型。下面我們對這個(gè)模型進(jìn)行簡單分析。
我們先研究G的一個(gè)連通分量K1。對于這個(gè)連通分量，可以先求出K1的生成樹T1。對于K1中的任意結(jié)點(diǎn)a，假如a在T1中的深度為奇數(shù)，我們就把a(bǔ)加入點(diǎn)集S1；否則我們把a(bǔ)加入點(diǎn)集S2（S1,S2最初為空集）。顯然最后S1,S2的交集為空。
不難證明，如果存在不同結(jié)點(diǎn)p和q，p和q同屬于S1或S2，而且G中存在邊(p,q)，那么要做到滿足題目要求的分組是不可能的，應(yīng)輸出No solution。否則，我們就得到了連通分量K1的唯一分組方案：分為S1,S2兩組。
對于G中的每個(gè)連通分量Ki，我們可以求出相應(yīng)的S1i,S2i。最后，我們的目的是把全部人分為2組。也就是說，對于i=1,2,3,...,m，我們必須決定把S1i中的人分到第1組，S2i中的人分到第2組，還是做剛好相反的處理。由于題目要求最后兩組的總?cè)藬?shù)差最小，我們可以用動態(tài)規(guī)劃的辦法來確定究竟選取上面的哪種決策。
不妨假設(shè)G中共有m個(gè)連通分量，記|S1i|=xi,|S2i|=yi(i=1,2,3,...,m)。若xi < yi，我們就交換xi和yi（這樣不影響結(jié)果的正確性）。記wi = xi - yi。那么只要對所有的wi做“半個(gè)背包”即可。也就是說，湊出盡量接近sum(wi)的數(shù)。接下去就非常簡單了。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-29 12:07:38
File Name: pku1112.cpp
Description:
************************************************************************/
#include <iostream>
#include <vector>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 110;
int n;
int g[maxn][maxn];
int cnt_id;
int id[maxn];
int w[maxn];
void dfs(int now, int new_id)
{
id[now] = new_id;
for (int i = 1; i <= n; i++) if (id[i] == 0 && g[now][i])
dfs(i, new_id);
}
void make_id()
{
cnt_id = 0;
memset(id, 0, sizeof(id));
for (int i = 1; i <= n; i++) if (id[i] == 0)
dfs(i, ++cnt_id);
}
int set_mask[maxn];
void divide(int cid, int now, int set_id, int *set_mask)
{
*(set_mask + now) = set_id;
for (int i = 1; i <= n; i++) if (*(set_mask + i) == 0 && id[i] == cid && g[now][i])
divide(cid, i, 3 - set_id, set_mask);
}
int ok()
{
memset(set_mask, 0, sizeof(set_mask));
for (int i = 1; i <= cnt_id; i++)
{
for (int j = 1; j <= n; j++)
if (id[j] == i)
{
divide(i, j, 1, set_mask);
break;
}
int cntx = 0;
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 1)
cntx++;
int cnty = 0;
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 2)
cnty++;
if (cntx < cnty)
{
for (int j = 1; j <= n; j++) if (id[j] == i)
set_mask[j] = 3 - set_mask[j];
}
w[i] = abs(cntx - cnty);
int flag = 1;
for (int j = 1; j <= n && flag; j++) if (id[j] == i && set_mask[j] == 1)
for (int k = 1; k <= n && flag; k++) if (id[k] == i && set_mask[k] == 1 && j != k)
if (g[j][k]) flag = 0;
for (int j = 1; j <= n && flag; j++) if (id[j] == i && set_mask[j] == 2)
for (int k = 1; k <= n && flag; k++) if (id[k] == i && set_mask[k] == 2 && j != k)
if (g[j][k]) flag = 0;
if (flag == 0) return 0;
}
return 1;
}
typedef struct ptr_t
{
int ptr, value;
};
ptr_t pre[maxn];
int mask[maxn];
void print(int now)
{
if (pre[now].value == 0)
return;
print(pre[now].ptr);
mask[pre[now].value] = 1;
}
void dp()
{
int f[maxn];
memset(f, 0, sizeof(f));
memset(pre, 0, sizeof(pre));
f[0] = 1;
int sum = 0;
for (int i = 1; i <= cnt_id; i++) sum += w[i];
for (int i = 0; i <= cnt_id; i++)
for (int j = sum / 2; j >= 0; j--) if (f[j] && !f[j + w[i]])
{
f[j + w[i]] = 1;
pre[j + w[i]].ptr = j;
pre[j + w[i]].value = i;
}
int ans_i;
for (int i = sum / 2; i >= 0; i--) if (f[i])
{
ans_i = i;
break;
}
memset(mask, 0, sizeof(mask));
print(ans_i);
int cnt1 = 0;
for (int i = 1; i <= cnt_id; i++)
{
if (mask[i])
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 1)
cnt1++;
}
else
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 2)
cnt1++;
}
}
printf("%d", cnt1);
for (int i = 1; i <= cnt_id; i++)
{
if (mask[i])
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 1)
printf(" %d", j);
}
else
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 2)
printf(" %d", j);
}
}
printf("\n");
int cnt2 = 0;
for (int i = 1; i <= cnt_id; i++)
{
if (mask[i])
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 2)
cnt2++;
}
else
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 1)
cnt2++;
}
}
printf("%d", cnt2);
for (int i = 1; i <= cnt_id; i++)
{
if (mask[i])
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 2)
printf(" %d", j);
}
else
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 1)
printf(" %d", j);
}
}
printf("\n");
}
int main()
{
int tmp[maxn][maxn];
while (scanf("%d", &n) != EOF)
{
memset(tmp, 0, sizeof(tmp));
for (int i = 1; i <= n; i++)
{
int t;
while (scanf("%d", &t), t != 0)
tmp[i][t] = 1;
}
memset(g, 0, sizeof(g));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && (tmp[i][j] == 0 || tmp[j][i] == 0))
g[i][j] = g[j][i] = 1;
make_id();
int t = ok();
if (!t)
printf("No solution\n");
else
dp();
}
return 0;
}