题意：现在有一群人，告诉你每个人都认识哪些人，让你将这一群人分成两组，其中每一组中的每个人都相互认识，并且使得两组中的人数尽量相近。问你是否能分成这样两组，如果不能输出No Solution ，否则输出人数最相近的方案。
注意你认识我不代表我认识你，组中的每一个人都必须是相互认识的。
首先建立由人和人认识关系构成的有向图，然后将其转化成一张无向图，如果两个点之间的边不是双向的，等于没有，所以就将其删去，保留双向边。然后对这个无向图求一次补图，形成的补图可能有多个联通块，并且位于不同联通块中的点是肯定可以放在一个组内的。
之后对于每个联通块，做一次二分图染色判定，判断其是否可以构成一张二分图。为什么要这么做，因为每个联通块中相邻的点是肯定不能放到一个组当中的，所以要对联通块做一次01染色，看看是否可以把当前的联通块分成两组，每一组中的人都不是相邻的。如果做完染色后发现该联通块不能构成一个二分图，那么肯定是No Solution，因为所有人都必须不是属于组1就是属于组2
做染色的同时统计每个联通块中奇点和偶点的数量，然后就可以来做背包了。建立一个容量为n/2的背包，对于每个联通块，我可以取里面所有的奇点也可以取里面所有的偶点，最后递归输出结果。
#include <cstdio> #include <sstream> #include <fstream> #include <cstring> #include <iostream> #include <algorithm> #include <map> #include <cctype> #include <ctime> #include <set> #include <climits> #include <vector> #include <queue> #include <stack> #include <cstdlib> #include <cmath> #include <string> #include <list> #define INPUT_FILE "in.txt" #define OUTPUT_FILE "out.txt" using namespace std; typedef long long LL; const int INF = INT_MAX / 2; void setfile() { freopen(INPUT_FILE,"r",stdin); freopen(OUTPUT_FILE,"w",stdout); } const int maxn = 105; struct Node { int cnt,e[maxn],col; }; Node node[maxn]; bool know[maxn],conflict,team1[maxn],vis[maxn]; bool g[maxn][maxn],dp[maxn * 2][maxn * 2]; int n,sz[maxn],sz_zero[maxn],sz_one[maxn],rcnt; int pid[maxn][maxn]; //染色 void dfs(int now,int id) { if(node[now].col == 0) sz_zero[id]++; else sz_one[id]++; pid[id][sz[id]++] = now; for(int i = 0;i < node[now].cnt;i++) { int nowid = node[now].e[i]; if(node[nowid].col == -1) { node[nowid].col = node[now].col ^ 1; dfs(nowid,id); } else { if(node[nowid].col == node[now].col) { conflict = true; } } } } //统计联通块并且进行染色 void judge() { rcnt = 0; for(int i = 1;i <= n;i++) { if(node[i].col == -1) { node[i].col = 0; rcnt++; dfs(i,rcnt); } } } //将第i个联通块中颜色为col的点加入组中 void addteam(int i,int col) { vis[i] = true; if(node[i].col == col) { team1[i] = true; } for(int j = 0;j < node[i].cnt;j++) { int chid = node[i].e[j]; if(vis[chid] == false) { addteam(chid,col); } } } //输出答案 void print_path(int i,int now) { if(i == 0) return; if(dp[i - 1][now - sz_zero[i]]) { memset(vis,0,sizeof(vis)); addteam(pid[i][0],0); print_path(i - 1,now - sz_zero[i]); } else { memset(vis,0,sizeof(vis)); addteam(pid[i][0],1); print_path(i - 1,now - sz_one[i]); } } void work() { dp[0][0] = true; //背包 for(int i = 1;i <= rcnt;i++) { for(int j = 0;j <= n;j++) { if(dp[i - 1][j] == true) { dp[i][j + sz_zero[i]] = true; dp[i][j + sz_one[i]] = true; } } } int val = -1; for(int j = n / 2;j >= 1;j--) { if(dp[rcnt][j] == true) { val = j; break; } } if(val == -1) { puts("No solution"); } else { print_path(rcnt,val); printf("%d",val); for(int i = 1;i <= n;i++) if(team1[i]) printf(" %d",i); printf(" %d",n - val); for(int i = 1;i <= n;i++) if(!team1[i]) printf(" %d",i); putchar(' '); } } int main() { int tmp; while(scanf("%d",&n) != EOF) { memset(node,0,sizeof(node)); memset(sz,0,sizeof(sz)); memset(sz_zero,0,sizeof(sz_zero)); memset(sz_one,0,sizeof(sz_one)); memset(dp,0,sizeof(dp)); memset(team1,0,sizeof(team1)); memset(g,0,sizeof(g)); //输入并且建立补图 for(int i = 1;i <= n;i++) { while(scanf("%d",&tmp),tmp) { g[i][tmp] = true; } node[i].col = -1; } for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if(!(g[i][j] && g[j][i]) && i != j) { node[i].e[node[i].cnt++] = j; } } } //染色并且统计联通块 conflict = false; judge(); if(conflict) { puts("No solution"); } else { work(); } } return 0; }