题目链接:http://poj.org/problem?id=1112
题目大意:把n个人分成两组;组内成员相互之间必须认识。做法是如果两个人不是相互都认识则建边,用dfs搜出连通分量,然后dp,具体见其他人的博客。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int f[Max],id;
int dp[Max][Max],mp[Max][Max];
int num[Max][2];
int cnt,tmp,co[Max],vst[Max],eid,p[Max],flag;
struct node
{
int to,next;
}e[2*Max*Max];
void addedge(int u,int v)
{
e[eid].to=v;
// e[eid].len=len;
e[eid].next=p[u];
p[u]=eid++;
}
void dfs(int u)
{
int v,i;
for(i=p[u];i!=-1;i=e[i].next)
{
v=e[i].to;
if(co[v]==co[u])
{
flag=1;
return;
}
else if(co[v]!=-1)
continue;
v=e[i].to;
f[v]=id;
co[v]=co[u]^1;
num[id][co[v]]++;
dfs(v);
if(flag)
return;
}
if(flag)
return;
}
int main()
{
int n,u,v,i,j;
// while(!=EOF)
// {
scanf("%d",&n);
memset(co,-1,sizeof(co));
memset(p,-1,sizeof(p));
eid=0;
for(i=1;i<=n;i++)
{
while(scanf("%d",&v),v)
{
mp[i][v]=1;
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(mp[i][j]&&mp[j][i])
continue;
if(i==j)
continue;
addedge(i,j);
addedge(j,i);
}
id=1;
flag=0;
// printf("yyyy");
for(i=1;i<=n;i++)
{
if(co[i]==-1)
{
co[i]=0;
num[id][0]++;
f[i]=id;
dfs(i);
// printf("cccc");
if(flag==1)
{
printf("No solution\n");
break;
}
id++;
}
}
if(flag)return 0;;
dp[0][0]=1;
for(i=1;i<id;i++)
{
//int tmp1=num[id][0];
// int tmp2=num[id][1];
for(j=0;j<=n/2;j++)
{
if(dp[i-1][j])
{
if(j+num[i][0]<=n/2)
dp[i][j+num[i][0]]=1;
if(j+num[i][1]<=n/2)
dp[i][j+num[i][1]]=1;
}
}
}
for(i=n/2;i>=0;i--)
{
if(dp[id-1][i]==1)
{
tmp=i;
cnt=i;
break;
}
}
for(i=id-1;i>=1;i--)
{
int typ;
if(tmp-num[i][0]>=0&&dp[i-1][tmp-num[i][0]])
{
typ=0;
tmp=tmp-num[i][0];//continue;
}
else if(tmp-num[i][1]>=0&&dp[i-1][tmp-num[i][1]])
{
tmp=tmp-num[i][1];
typ=1;
}
for(j=1;j<=n;j++)
{
if(f[j]==i&&co[j]==typ)
vst[j]=1;
}
}
printf("%d ",cnt);
for(i=1;i<=n;i++)
{
if(vst[i])
printf("%d ",i);
}
puts("");
printf("%d ",n-cnt);
for(i=1;i<=n;i++)
{
if(!vst[i])
printf("%d ",i);
}
puts("");
// }
}
分享到:
相关推荐
北大POJ3087-Shuffle'm Up 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ 1328 java做!雷达问题!java版本!AC答案~
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码