引用discuss里的一句话，好辣的一道题目。。。
一定要注意认识的关系不是互相的，先建图，把不是互相认识的人连边，然后二分图染色，把原图分成m个块，再用类似背包的东西分f[i][j][k]表示前i个块，team1有j个人，team2有k个人能否实现，注意记录一下路径，然后递归输出就可以了，题目不算很难，但是细节比较多，涉及到的东西也挺多，挺容易出错的。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<cstdlib>
#include<cmath>
using
namespace std;
#define ll long long
#define pb push_back
const int maxn
= 102;
vector<int>q[maxn];
bool s[maxn];
int
a[maxn][4];
vector<int>b[maxn][4];
int
t[maxn],g[maxn][maxn][maxn];
int m,n;
bool
v[maxn][maxn],e[maxn][maxn];
bool f[maxn][maxn][maxn];
void solve(int
x,int y)
{
for (int i = 0; i < q[x].size(); i++)
if
(s[q[x][i]] == 0)
{
s[q[x][i]] = 1;
a[m][y]++;
b[m][y].pb(q[x][i]);
solve(q[x][i],3 - y);
}
}
void dfs(int now,int x,int y)
{
if (now == 0) return;
t[now] = g[now][x][y];
if (t[now] == 1) dfs(now - 1,x - a[now][1],y -
a[now][2]);
else dfs(now - 1,x - a[now][2],y - a[now][1]);
}
bool
check(int x,int y)
{
for (int i = 0; i < b[x][y].size(); i++)
for (int j = 0; j < b[x][y].size(); j++)
if (b[x][y][i] !=
b[x][y][j] && e[b[x][y][i]][b[x][y][j]]) return 1;
return
0;
}
int main()
{
while (scanf("%d",&n) != EOF)
{
for (int i = 1; i <= n; i++) q[i].clear();
memset(v,0,sizeof(v));
memset(e,0,sizeof(e));
int x;
for (int i = 1; i <= n; i++)
{
while
(scanf("%d",&x) && x != 0) v[i][x] = 1;
}
//for (int i = 1; i <= n;i++)
//for (int j = 1; j <= n;
j++) if (v[i][j]) cout<<i<<" "<<j<<endl;
//return 0;
for (int i = 1; i <= n; i++)
for (int j
= i + 1; j <= n; j++)
{
if (v[i][j] &&
v[j][i]) continue;
q[i].pb(j);
q[j].pb(i);
e[i][j] = e[j][i] = 1;
}
/*for (int i = 1; i<=
n; i++)
{
cout<<i<<" ";
for
(int j = 0; j < q[i].size(); j++) cout<<q[i][j]<<" ";
cout<<endl;
}*/
//return 0;
memset(s,0,sizeof(s));
memset(s,0,sizeof(s));
memset(a,0,sizeof(a));
m = 0;
for (int i = 1; i <= n;
i++)
for (int j = 1; j <= 2; j++) b[i][j].clear();
for (int i = 1; i <= n; i++)
if (s[i] == 0)
{
s[i] = 1;
m++;
a[m][1]++;
b[m][1].pb(i);
solve(i,2);
}
bool flag =
0;
for (int i = 1; i <= m; i++)
{
if
(check(i,2) || check(i,1))
{
flag = 1;
break;
}
}
if (flag)
{
puts("No solution");
continue;
}
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
f[0][0][0] = 1;
//return 0;
for (int i = 1; i <= m;
i++)
for (int j = 0; j <= n; j++)
for (int
k = 0; k <= n; k++)
if (j + k <= n)
{
if (j - a[i][1] >= 0 && k - a[i][2] >= 0
&& f[i - 1][j - a[i][1]][k - a[i][2]])
{
f[i][j][k] = 1;
g[i][j][k] = 1;
}
if (j - a[i][2] >= 0 && k - a[i][1] >= 0
&& f[i - 1][j - a[i][2]][k - a[i][1]])
{
f[i][j][k] = 1;
g[i][j][k] = 2;
}
}
int maxx = 10000,fir = 0,sec = 0;
for (int i = 1; i <= n - 1; i++)
{
int j = n -
i;
if (f[m][i][j] && maxx > abs(i - j))
{
maxx = abs(i - j);
fir = i; sec
= j;
}
}
memset(t,0,sizeof(t));
dfs(m,fir,sec);
memset(s,0,sizeof(s));
int ans = 0;
for (int i = 1; i <= m; i++)
if (t[i] == 1)
{
ans = ans + b[i][1].size();
for (int j
= 0; j < b[i][1].size(); j++) s[b[i][1][j]] = 1;
}
else
{
ans = ans + b[i][2].size();
for (int j = 0; j < b[i][2].size(); j++) s[b[i][2][j]] = 1;
}
if (ans == n || ans == 0)
{
puts("No solution");
continue;
}
printf("%d",ans);
for (int i = 1; i <= n; i++)
if
(s[i]) printf(" %d",i);
printf("\n");
printf("%d",n -
ans);
for (int i = 1; i <= n; i++)
if (!s[i])
printf(" %d",i);
printf("\n");
}
return
0;
}
POJ 1112 Team Them Up!,布布扣,bubuko.com
原文：http://www.cnblogs.com/yuhao1994/p/3578149.html