对抗赛
Time Limit:1000MS Memory Limit:65536K
Total Submit:118 Accepted:6
Description
今年大量新成员的加入给软件协会注入新鲜血液。张女侠，吴大牛和姚大牛主要负责新成员的训练工作。
经过一个暑假的训练，新成员都有了不同程度的成长。为了检测新成员的训练成果，软件协会竞赛部部长决定举行一次新成员对抗赛。比赛分成两队：红队和蓝队。吴大牛和姚大牛各带领一支队伍，张女侠做裁判。
为了公平起见，新成员中互相认识的成员要分在不同队伍，并且两支队伍的人数要相同。每个人有一个编号，编号范围为1—N。
Input
有多组测试数据，每组测试数据第一行为N M，表示共有N人，M对关系。接下来输入M行，每行两个数X和Y，表示X和Y认识(1<=N<=50,1<=M<=100,1<=X,Y<=N且X!=Y)
Output
若可以分配成功进行比赛，输出"Yes!"，否则输出"No!"(不包括引号)
Sample Input
20 10
1 11
2 12
3 13
4 14
5 15
6 16
7 17
8 18
9 19
10 20
Sample Output
Yes!
Source
-----------------------------------------------------
最近在看二分匹配，一开始还以为是二分匹配题，囧。。。。
思路完全错误了。。。唉。。
赛后听小雨讲解了下才明白就是：并查集+dfs
思路：用并查集把N个人分成一个个连通集合(就是一棵树)，然后用每个连通集再分成两个部分(根据在这棵树中的层数是奇数还是偶数)term[i][0]存第i棵树中层数为偶数的人数，term[i][1]存第i棵树中层数为奇数的人数，然后直接对T个连通集dfs，看是否能使0队和1队的个数都小于等于N/2;
//算法：并查集+dfs
//AC代码：0ms
#include <iostream>
int N,M,T,flag;
int p[105];//储存父节点
int mark[105];//用来标记是否是根节点
int team[105][2];//临时储存
int team1[105][2];//最终每个储存连通图
int find_set(int x)//找父节点
{
if(p[x]!=x)
return find_set(p[x]);//只找父节点，不更新
/*这样会WA*/
//p[x]=find_set(p[x]);
//return p[x];
}
int get_degree(int x,int d)//返回层数
{
if(p[x]==x)
return d;
return get_degree(p[x],d+1);
}
void dfs(int k,int s0,int s1)//深搜
{
if(flag)
return;
if(k==T+1)
{
if(s0<=N/2&&s1<=N/2)
flag=1;
return;
}
if(s0>N/2||s1>N/2)
return;
dfs(k+1,s0+team1[k][0],s1+team1[k][1]);
if(flag)//剪枝
return;
dfs(k+1,s0+team1[k][1],s1+team1[k][0]);
return;
}
int main()
{
int i,x,y,dx,dy,fx,fy;
while(scanf("%d%d",&N,&M)!=EOF)
{
flag=0;
memset(mark,0,sizeof(mark));
memset(team,0,sizeof(team));
for(i=1;i<=N;i++)
p[i]=i;
for(i=1;i<=M;i++)
{
scanf("%d%d",&x,&y);
if(flag)
continue;
dx=get_degree(x,1);
dy=get_degree(y,1);
fx=find_set(x);
fy=find_set(y);
if(fx==fy)//在同个树上
{
if((dx+dy)%2==0)//如果层数相差为偶数，则直接flag=1，即输"No!"
flag=1;
}
else
{
if((dx+dy)%2==0)//(1)层数奇偶性相同，就根节点相连
{p[fx]=fy;mark[fy]=1;}
else//(2)奇偶性不同，就把奇数的根节点连在偶数的当前结点后面
{
if(dx&1)
{p[fx]=y;mark[y]=1;}
else
{p[fy]=x;mark[x]=1;}
}
}
}
if(N&1||flag)//提前判断
{printf("No!/n");continue;}
int dans=0;
for(i=1;i<=N;i++)
{
fx=find_set(i);
dx=get_degree(i,1);
//printf("%d-",dx);
if(dx==1&&fx==i&&!mark[i])
dans++;
else
{
if(dx&1)
team[fx][1]++;
else
team[fx][0]++;
}
}
//printf("%d-",get_degree(7,1));
if(dans>=N/2)//如果孤立点数>=N/2就直接输出"Yes!"
{printf("Yes!/n");continue;}
T=0;
for(i=1;i<=N;i++)
{
if(team[i][0]||team[i][1])
{
T++;
team1[T][0]=team[i][0];
team1[T][1]=team[i][1];
//printf("%d-%d/n",team1[T][0],team1[T][1]);
}
}
dfs(1,0,0);
if(flag)
printf("Yes!/n");
else
printf("No!/n");
}
return 0;
}