【Link】:

【Description】



给你n个人;

有一些人之间有认识关系

a认识b,b不一定认识a

让你把这n个人分成两组

使得这两组中的每一组:

组内的人与人之间都相互认识.

并且,使得两组的人数之差尽可能小;

输出分组的方案;

【Solution】



如果A和B不是相互认识

那么他们俩肯定是在不同的组

则,在不是相互认识的人之间建一条边;

这样就能形成一张图了;

并且可能有多个连通块

然后,对每个连通块做二分染色;

如果都能做二分染色;

有解

这样,每个连通块都有的点被染成0,有的被染成1

我们相当于要对每个连通块都做出决策

到底是把0放到A组,1放到B组

还是把0放到B组,1放到A组;

动态规划;

设f[i][j]表示前i个连通块,A组的人数比B组多j的情况是否能得到;

设x为第i+1个连通块0的个数,y为第i+1个连通块1的个数;

如果f[i][j]==1



f[i+1][j+x−y]=1

f[i+1][j+y−x]=1

两个赋值,对应了两种决策;

最后j从0..n枚举

找最小的f[tot][abs(j)]==1的j;

然后递归获得方案即可;

需要用一个数组记录方案



【NumberOf WA】



0



【Reviw】



图论模型的转化.

动态规划解决问题。



【Code】

#include <bits/stdc++.h>
using namespace std; const int N = 100; vector <int> G[N+10],v[2];
map <int,int> dic[N+10];
map <int,pair<int,pair<int,int> > > pre[N+10];
int n,g[N+10][N+10],a[N+10][2],cnt[2],tot,idx;
pair <int,int> color[N+10];
pair <int,int> temp; bool dfs(int x,int p){
color[x] = make_pair(p,idx);
cnt[p]++;
bool ok = true;
int len = G[x].size();
for (int i = 0; i <= len-1;i++){
int y = G[x][i];
if (color[y].first!=-1){
if (color[y].first != (1-p))
ok = false;
}else
ok =ok && dfs(y,1-p);
}
return ok;
} void print(int now,int j){
if (now==0) return;
int xx = pre[now][j].second.first,yy = pre[now][j].second.second;
for (int i = 1;i <= n;i++)
if (color[i].second==now){
if (color[i].first == 0)
v[xx].push_back(i);
else
v[yy].push_back(i);
}
print(now-1,pre[now][j].first);
} int main()
{
//freopen("F:\\rush.txt","r",stdin);
int T;
scanf("%d",&T);
while (T--){
for (int i = 1;i <= N;i++) {
G[i].clear();
a[i][0] = a[i][1] = 0;
color[i] = make_pair(-1,0);
dic[i].clear();
} for (int i = 1;i <= N;i++)
for (int j = 1;j <= N;j++)
g[i][j] = 0; scanf("%d",&n);
for (int i = 1;i <= n;i++){
int x;
scanf("%d",&x);
while (x!=0){
g[i][x] = 1;
scanf("%d",&x);
}
} for (int i = 1;i <= n;i++)
for (int j = i+1;j <= n;j++){
if (g[i][j] && g[j][i]) continue;
G[i].push_back(j),G[j].push_back(i);
} tot = 0;
bool sol = true;
for (int i = 1;i <= n;i++)
if (color[i].first==-1){
cnt[0] = cnt[1] = 0;
idx = ++tot;
sol = sol && dfs(i,0);
a[tot][0] = cnt[0];
a[tot][1] = cnt[1];
} if (!sol){
puts("No solution");
puts("");
continue;
} dic[0][0] = 1;
for (int i = 0;i <= tot-1;i++)
for (int j = -n;j <= n;j++)
if (dic[i][j]){
int x = a[i+1][0],y = a[i+1][1];
int t = x-y;
if (!dic[i+1][j+t]){
dic[i+1][j+t] = 1;
pre[i+1][j+t] = make_pair(j,make_pair(0,1));
}
if (!dic[i+1][j-t]){
dic[i+1][j-t] = 1;
pre[i+1][j-t] = make_pair(j,make_pair(1,0));
}
} v[0].clear(),v[1].clear();
for (int j = 0;j <= n;j++){
if (dic[tot][j]){
print(tot,j);
break;
}
if (dic[tot][-j]){
print(tot,j);
break;
}
} if (v[0].empty() || v[1].empty())
puts("No solution");
else
for (int t = 0;t <= 1;t++){
printf("%d ",(int) v[t].size());
for (int i = 0;i <= (int) v[t].size()-1;i++){
printf("%d",v[t][i]);
if (i==(int) v[t].size()-1)
puts("");
else
putchar(' ');
}
}
puts("");
}
return 0;
}
05-11 22:18