UVa 1627 Team them up!

题目

◇题目传送门◆（由于UVa较慢，这里提供一份vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

有$N$个人，需要将他们分成两组，使得每个人都被分到其中一组，且要求同组的人相互认识。要求两组成员数尽可能接近。多解时输出任意方案，无解输出No Solution。

注意：若两个人中1认识2，但2是不认识1的！！

思路

设两个组的编号为0和1。因为同组内人是相互认识的，所以若有两个人不是相互认识的，则他们应被分到不同的组。所以，若已知一个人在第0组，则所有不认识他的人都应分到第1组；而不认识这些人的所有人都应该分到第0组……以此类推。是不是有点像二分图？？？

没错！就是二分图。

我们将所有的不相互认识的关系看成一个图，则对于每个连通分量，我们应对它进行二分图判定。注意：若在判定中遇到矛盾，则该问题无解。

举个例子：对于第二个样例，我们可以画出如下的图：

对于连通分量$\{1,3,4,5\}$，若$1$在组0，则可推出$3,4,5$在组1；反之，若$1$在组1，则$3,4,5$在组0。设组0的人数比组1的人数多$d$个，可推出：

可以看到，每个连通分量的两种情况分别对应$d$加或减一个值，而我们的最终目标是让$d$的绝对值尽可能的小。你想到了什么？01背包？？

没错！就是一个01背包问题，只是这个问题没有体积，而重量有正有负。最后我们要找的也不是重量最大，而是最接近0！

记$d[i]$为在一个连通分量内组0比组1的人数多出的人数。

我们定义状态$f[i][j]$为已经考虑到连通分量$i$，且两组相差$j$的情况是否存在，则可列出状态转移方程：

其中，边界条件为$f[0][0]=0$。

注意，因为$j$属于$[-N,N]$中，所以我们需要坐标平移。

最终按绝对值大小枚举答案，判断该状态是否存在。

正解代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=100;int N;
bool G[Maxn+5][Maxn+5];
int ccnt,col[Maxn+5];
vector<int> team[Maxn+5][2];
int diff[Maxn+5];
bool f[Maxn+5][2*Maxn+5];bool DFS(int u,int c) {col[u]=c;team[ccnt][c-1].push_back(u);for(int v=0;v<N;v++)if(u!=v&&!(G[u][v]&&G[v][u])) {if(col[v]>0&&col[u]==col[v])return false;if(!col[v]&&!DFS(v,3-c))return false;}return true;
}//二分图判定
bool BuildGraph() {ccnt=0;memset(col,0,sizeof col);for(int i=0;i<N;i++)if(!col[i]) {team[ccnt][0].clear();team[ccnt][1].clear();if(!DFS(i,1))return false;diff[ccnt]=team[ccnt][0].size()-team[ccnt][1].size();ccnt++;}return true;
}//对每个连通分量进行判定void Print(int ans) {vector<int> team1,team2;for(int i=ccnt-1;i>=0;i--) {int t;if(f[i][ans-diff[i]+N]) {t=0;ans-=diff[i];} else {t=1;ans+=diff[i];}for(int j=0;j<team[i][t].size();j++)team1.push_back(team[i][t][j]);for(int j=0;j<team[i][t^1].size();j++)team2.push_back(team[i][t^1][j]);}//找出答案printf("%d",team1.size());for(int i=0;i<team1.size();i++)printf(" %d",team1[i]+1);puts("");printf("%d",team2.size());for(int i=0;i<team2.size();i++)printf(" %d",team2[i]+1);puts("");
}
void Solve() {memset(f,false,sizeof f);f[0][0+N]=true;for(int i=0;i<ccnt;i++)for(int j=-N;j<=N;j++)if(f[i][j+N]) {f[i+1][j+N+diff[i]]=true;f[i+1][j+N-diff[i]]=true;}for(int i=0;i<=N;i++) {if(f[ccnt][i+N]) {Print(i);return;}if(f[ccnt][N-i]) {Print(-i);return;}}/枚举答案位置
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint T;scanf("%d",&T);while(T--) {scanf("%d",&N);for(int i=0;i<N;i++) {int x;while(scanf("%d",&x)!=EOF&&x)G[i][x-1]=true;}if(N==1||!BuildGraph())puts("No solution");//注意特判N=1的情况else Solve();if(T)puts("");memset(G,0,sizeof G);}return 0;
}