【★】Team Them Up!

发表于   |   分类于

POJ 1112

Team Them Up! Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 2348 Accepted: 610 Special Judge

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



1 划分集合
对于第i个人，将i划入S[0]，所有i不认识的人和所有不认识i的人划入S[1]；
然后将S[1]中所有人按上述步骤递归做下去；
这样就划分出两个集合，S[0]和S[1]中的任何一个人都不能加入另外一组，否则矛盾。
然后对剩余的人重复以上步骤，这样划分出一组集合对（内含两个集合），其中任何
一个集合对中的人认识其他集合对中的所有人，并被其他集合对中所有人认识。

2 合并
任何 一个集合对中的人认识其他集合对中的所有人，并被其他集合对中所有人认识，
因此可以将两个集合对随意合并，合并后仍然保持这一特性。例如：pair( (a),(b) )与pair( (c),(d) )，可以
合并成pair( (a,c), (b,d) )，也可以先交换(c)和(d)的顺序，再合并成pair( (a,d), (b,c) )。
因此问题转化为如何合并，使得最终合并后的集合对中两个集合的元素数目之差最小。
将第i个集合对中两个集合的元素数目之差记为di，则对于数组d1,d2,d3,…, dn，
sum += di表示第i个集合对可直接被合并，
sum += -di表示需先交换第i个集合对中的两个集合，再参与合并。
问题转化为如何求得sum的最小值？利用动态规划求解（类似0-1背包问题），参见dfs()函数。

// author: jfo()

////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cassert>
using namespace std;

int N;
int A[101][101];
int S[2][101];
set<int> IDs;
typedef vector<int> VI;
typedef vector<pair<VI, VI> > VP;
VP V;
VI C;
VI out[2];
int m = 100;
int pos;

int check()
{
for(int k = 0; k < 2; k++) {
VI::iterator iter = out[k].begin();
VI::iterator e = out[k].end();
for(; iter != e; ++iter) {
//assert(out[0][iter] + out[1][iter] < 2);
//if(out[0][iter] + out[1][iter] > 1)
// return 0;
for(VI::iterator iter2 = iter + 1; iter2 != e; ++iter2) {
if(!A[iter][iter2] || !A[iter2][iter])
return 0;
}
}
}
return 1;
}

void fn_bfs(int id, int cur_set)
{
if(S[cur_set][id])
return;

S[cur_set][id] = 1;
IDs.erase(id);

int i;
int comp_set = 1 - cur_set;
vector<int> t;
for(i = 1; i <= N; i++) {
if(i == id)
continue;
// id don’t know i
if(!A[id][i] && !S[comp_set][i]) {
S[comp_set][i] = 1;
t.push_back(i);
}
// i don’t know id
if(!A[i][id] && !S[comp_set][i]) {
S[comp_set][i] = 1;
t.push_back(i);
}
}
for(i = 0; i < t.size(); i++) {
S[comp_set][t[i]] = 0;
fn_bfs(t[i], comp_set);
}
}

void fn_dfs(int id, int cur_set)
{
if(S[cur_set][id])
return;

S[cur_set][id] = 1;
IDs.erase(id);

int i;
int comp_set = 1 - cur_set;
for(i = 1; i <= N; i++) {
if(i == id)
continue;
// id don’t know i
if(!A[id][i] && !S[comp_set][i])
fn_dfs(i, comp_set);
// i don’t know id
if(!A[i][id] && !S[comp_set][i])
fn_dfs(i, comp_set);
}
}

void reap()
{
V.push_back(make_pair(VI(), VI()));
pair<VI,VI>& p = V.back();
for(int i = 1; i <= N; i++) {
if(S[0][i])
p.first.push_back(i);
if(S[1][i])
p.second.push_back(i);
}
if(p.first.size() < p.second.size())
swap(p.first, p.second);
C.push_back(p.first.size() - p.second.size());
memset(&S[0][0], 0, sizeof(S[0]));
memset(&S[1][0], 0, sizeof(S[1]));
}

int f[100][200];
int dfs(int index, int val)
{
if(index < 0)
return val;

if(abs(f[index][val + 100]) < 101)
return f[index][val + 100];

int v = 101;
if(!val) {
v = dfs(index - 1, C[index]);
}
else {
int t = C[index];
int a = dfs(index - 1, val + t);
int b = dfs(index - 1, val - t);
v = abs(a) > abs(b) ? b : a;
}
f[index][100 + val] = v;
return v;
}

void merge()
{
int i;
for(i = 0; i < C.size(); i++) {
for(int j = 0; j < 200; j++)
f[i][j] = 101;
}
dfs(C.size() - 1, 0);

int v = 0;
for(i = C.size() - 1; i > 0; i–) {
if(f[i][100 + v] == f[i-1][100 + v + C[i]]) {
out[0].insert(out[0].end(), V[i].first.begin(), V[i].first.end());
out[1].insert(out[1].end(), V[i].second.begin(), V[i].second.end());
v = v + C[i];
}
else if(f[i][100 + v] == f[i-1][100 + v - C[i]]) {
out[0].insert(out[0].end(), V[i].second.begin(), V[i].second.end());
out[1].insert(out[1].end(), V[i].first.begin(), V[i].first.end());
v = v - C[i];
}
}
if(f[i][100 + v] == v + C[i]) {
out[0].insert(out[0].end(), V[i].first.begin(), V[i].first.end());
out[1].insert(out[1].end(), V[i].second.begin(), V[i].second.end());
}
else if(f[i][100 + v] == v - C[i]) {
out[0].insert(out[0].end(), V[i].second.begin(), V[i].second.end());
out[1].insert(out[1].end(), V[i].first.begin(), V[i].first.end());
}
}

int solve()
{
for(int i = 1; i <= N; i++)
IDs.insert(i);
fn_dfs(pos, 0); // or fn_bfs(pos, 0);
reap();
while(!IDs.empty()) {
fn_dfs(*IDs.begin(), 0);
reap();
}
merge();
if(!check())
return 0;
sort(out[0].begin(), out[0].end());
sort(out[1].begin(), out[1].end());
return 1;
}

int main()
{
cin >> N;
int f;
for(int i = 1; i <= N; i++) {
int c = 0;
cin >> f;
while(f) {
A[i][f] = 1;
c++;
cin >> f;
}
if(c < m) {
m = c;
pos = i;
}
}
if(solve()) {
cout << out[0].size() << " ";
copy(out[0].begin(), out[0].end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << out[1].size() << " ";
copy(out[1].begin(), out[1].end(), ostream_iterator<int>(cout, " "));
cout << endl;
}
else
cout << "No solution" << endl;
return 0;
}