POJ 1112 Team Them Up!

本文主要是介绍POJ 1112 Team Them Up!，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=1112

题意：一共N个人，给出每个人和其余人是否认识，把所有人分成两组。
要求1）每一个人 属于其中一组。
2）每组必须有人 
3）每组内的所有人 必须相互认识（有向边 相互认识 才是认识） 
4)两组的人数之差尽可能小

先读入数据，把两两不认识的人 连边， 建图，则同一边连接的两点不能在同一组。建完图后，进行DFS 染色，可以把图 分成sum个连通分量，每个联通分量的点 标记 0 1 交替，如果出现同一边的两点 标记相同，则无法分到两个组中，"No solution".
每个连通分量，有两个组即0 和1 分别标记的，两点集的人必须分到不同的小组。

之后DP， dp[i][j][k]  i代表分配第i个联通分量，j代表两组的人数差此时为j，k有三个值：0 记录路径 由上一个联通块的差值j得到， 1 代表 此时最终求的 两组 哪个组(0 or 1)人数少， 2 代表 这次把第i个联通分量的 个数少的点集 分到 哪一组。
dp[i-1][j][]可以推出 dp[i][j+cha][] dp[i][abs(j-cha)][] , //cha 是这个联通分量内0 1 标记的两点集人数的差值。
最后找dp[sum][i][0] i由0到n 找dp的值存在的最小的i，
之后进行DFS 输出路径

发现dp是硬伤。。

code:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 1000000000
#define N 103
int d[N][N],n,tot,hh[N],sum,vis[N],s[N][3],sss[N][3][N],flag,mar[N],dp[N][N][3];
int out[2][N],ar[2];
struct node
{int u,v,next;
}edge[2*N*N];
void add(int u,int v)
{edge[tot].u=u; edge[tot].v=v;edge[tot].next=hh[u]; hh[u]=tot++;
}
void dfs(int u,int mark,int ss,int last)
{if(flag) return ;vis[u]=1;mar[u]=mark;s[ss][mark]++;int cou=s[ss][mark];sss[ss][mark][cou]=u;for(int i=hh[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v==last) continue;if(vis[v]){if(mar[v]==mark){flag=1; return ;}continue;}dfs(v,!mark,ss,u);}
}
void dfss(int x,int y)
{if(x<=0) return;int a1=dp[x][y][0],a2=dp[x][y][2];if(s[x][0]<s[x][1]){for(int i=1;i<=s[x][0];i++)out[a2][++ar[a2]]=sss[x][0][i];for(int i=1;i<=s[x][1];i++)out[a2^1][++ar[a2^1]]=sss[x][1][i];}else{for(int i=1;i<=s[x][0];i++)out[a2^1][++ar[a2^1]]=sss[x][0][i];for(int i=1;i<=s[x][1];i++)out[a2][++ar[a2]]=sss[x][1][i];}dfss(x-1,a1);
}
int main()
{while(scanf("%d",&n)!=EOF){memset(d,0,sizeof(d));for(int i=1;i<=n;i++){int a;while(scanf("%d",&a),a)d[i][a]=1;}tot=0;memset(hh,-1,sizeof(hh));for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(d[i][j] && d[j][i]) continue;add(i,j); add(j,i);}}sum=0; memset(vis,0,sizeof(vis));memset(s,0,sizeof(s));memset(mar,-1,sizeof(mar));flag=0;for(int i=1;i<=n;i++){if(vis[i]) continue;sum++;// from 1dfs(i,0,sum,-1);}if(flag){printf("No solution\n"); continue;}memset(dp,-1,sizeof(dp));dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=0;for(int i=1;i<=sum;i++){for(int j=0;j<=n;j++){if(dp[i-1][j][0]>=0){int cha=abs(s[i][0]-s[i][1]);dp[i][j+cha][0]=j;dp[i][j+cha][1]=dp[i-1][j][1];dp[i][j+cha][2]=dp[i-1][j][1];if(j>cha){dp[i][j-cha][0]=j;dp[i][j-cha][1]=dp[i-1][j][1];dp[i][j-cha][2]=dp[i-1][j][1]^1;}else{dp[i][cha-j][0]=j;dp[i][cha-j][1]=dp[i-1][j][1]^1;dp[i][cha-j][2]=dp[i-1][j][1]^1;}}}}ar[0]=ar[1]=0;for(int i=0;i<=n;i++){if(dp[sum][i][0]>=0){dfss(sum,i);printf("%d",ar[0]);for(int i=1;i<=ar[0];i++) printf(" %d",out[0][i]);puts("");printf("%d",ar[1]);for(int i=1;i<=ar[1];i++) printf(" %d",out[1][i]);puts("");break;}}}return 0;
}

这篇关于POJ 1112 Team Them Up!的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---