题意:
给出n个人以及认识其他人的情况,现在要把所有人分成两队,每队至少一人,求使两队人数差距最小且每队内部的人都相互认识的分队情况。
分析:
这道题让我学习到了不少,首先看到使差距最小就想到了背包,但是不会表示分队情况。看了别人的思路,这个很明显是要判断是否是二分图,让不是相互认识的两人连一条边,若不是二分图则不能分成两队。利用染色法判断二分图,则每个连通分量都包含0,1两个集合。
dp[i][j]表示i个联通分量能组成符合条件的人数为j的一队,par[i][j]记录路径
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define N 110
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
int n,tim,num;
int dp[N][N],par[N][N],mapc[N][N],part[N][];
int color[N],dfn[N],f[N],road[N][N][];
vector<int>e[N];
int dfs(int u){
dfn[u]=++tim;
road[num][++part[num][color[u]]][color[u]]=u;
for(int i=;i<e[u].size();++i){
int v=e[u][i];
if(dfn[v]==){
color[v]=(!color[u]);
if(dfs(v)==)return ;
}
else{
if(v!=u&&color[u]==color[v])return ;
}
}
return ;
}
void hand(){
int v;
for(v=n/;v>=;--v){
if(dp[num][v])
break;
}
if(v==){printf("No solution\n");return;}
memset(f,,sizeof(f));
int tmp=v,t;
for(int i=num;i>=;--i){
t=par[i][tmp];
tmp-=part[i][t];
for(int j=;j<=part[i][t];++j)
f[road[i][j][t]]=;
}
printf("%d",v);
for(int i=;i<=n;++i)
if(f[i])
printf(" %d",i);
printf("\n");
printf("%d",n-v);
for(int i=;i<=n;++i)
if(!f[i])
printf(" %d",i);
printf("\n");
}
void solve(){
memset(part,,sizeof(part));
memset(color,,sizeof(color));
memset(dfn,,sizeof(dfn));
memset(dp,,sizeof(dp));
tim=num=;
int k;
for(k=;k<=n;++k){
if(!dfn[k]){
++num;
if(dfs(k)==)break;
}
}
if(k<=n)printf("No solution\n");
else{
dp[][]=;
for(int i=;i<=num;++i)
for(int j=;j<=n/;++j){
int tmp=j-part[i][];
if(tmp>=&&dp[i-][tmp]){
dp[i][j]=;
par[i][j]=;
}
tmp=j-part[i][];
if(tmp>=&&dp[i-][tmp])
{
dp[i][j]=;
par[i][j]=;
}
}
hand();
}
}
int main()
{
int ca=;
scanf("%d",&ca);
while(ca--){
scanf("%d",&n);
int a;
memset(mapc,,sizeof(mapc));
for(int i=;i<=n;++i)
e[i].clear();
for(int i=;i<=n;++i){
while(~scanf("%d",&a)&&a){
mapc[i][a]=;
}
}
for(int i=;i<=n;++i)
for(int j=i+;j<=n;++j)
if(mapc[i][j]==||mapc[j][i]==){
e[i].push_back(j);
e[j].push_back(i);
}
solve();
if(ca)printf("\n");
}
return ;
}