【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;
}