【poj1112】 Team Them Up!

http://poj.org/problem?id=1112 (题目链接)

题意

　　将n个人分成两组，每个人有认识的人，要求每一组中的人互相认识，并且两组人数之差尽可能的小，求如何分。

Solution

　　二分图染色的裸题，比较麻烦的是dp统计答案。。下午急着去打球，照着hzwer的程序码了一遍。

代码

// poj1112

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<vector>

#include<cmath>

#define LL long long

#define MOD 100000000

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=200;

struct edge {int to,next;}e[maxn*maxn];

struct data {int x,y;}s[maxn];

vector<int> id[maxn][2],ans[2];

int f[maxn][maxn<<1],g[maxn][maxn<<1],head[maxn],c[maxn],ss[2],b[maxn];

int cnt,num,n;

void link(int u,int v) {

	e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;

	e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;

}

bool color(int x,int f) {

	c[x]=f;ss[f]++;

	id[num][f].push_back(x);

	for (int i=head[x];i;i=e[i].next) {

		if (c[e[i].to]==-1) {

			if (!color(e[i].to,f^1)) return 0;

		}

		else if (c[e[i].to]==f) return 0;

	}

	return 1;

}

void print(int k,int x) {

	if (!k) return;

	int t=g[k][x];

	for (int i=0;i<2;i++)

		for (int j=0;j<id[k][i].size();j++)

			ans[i^t].push_back(id[k][i][j]);

	print(k-1,x+id[k][t].size()-id[k][t^1].size());

}

int main() {

	scanf("%d",&n);

	memset(c,-1,sizeof(c));

	for (int x,i=1;i<=n;i++) {

		for (int j=1;j<=n;j++) b[j]=0;

		while (scanf("%d",&x)!=EOF && x) b[x]=1;

		for (int j=1;j<=n;j++) if (!b[j] && j!=i) link(i,j);

	}

	for (int i=1;i<=n;i++) if (c[i]==-1) {

			ss[0]=ss[1]=0;num++;

			if (!color(i,0)) {printf("No solution");return 0;}

			s[num]=(data){ss[0],ss[1]};

		}

	f[0][100]=1;

	for (int i=1;i<=num;i++)

		for (int j=0;j<=200;j++) if (f[i-1][j]) {

				int x=s[i].x,y=s[i].y;

				f[i][j+x-y]=1;

				f[i][j+y-x]=1;

				g[i][j+x-y]=1;

				g[i][j+y-x]=0;

			}

	for (int i=0;i<=100;i++) if (f[num][100-i]) {

			print(num,i+100);

			break;

		}

	printf("%d ",ans[0].size());

	for (int i=0;i<ans[0].size();i++) printf("%d ",ans[0][i]);

	printf("\n%d ",ans[1].size());

	for (int i=0;i<ans[1].size();i++) printf("%d ",ans[1][i]);

	return 0;

}