注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu1287.分考场  

2011-11-27 10:42:53|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1287.分考场
Time Limit: 1000 MS         Memory Limit: 65536 K
Total Submissions: 73 (21 users)         Accepted: 20 (17 users)
[ My Solution ]

Description

期末考试的时候,老师要把全班学生分在两个考场。老师在分考场的时候要考虑尽量避免把相互之间比较熟悉的同学分在不同的考场,因为他们可能会联合起来作弊。现在老师统计了同学们相互之间熟悉情况,他想知道能否合理地分考场,将所有相互熟悉的同学分在不同的考场。

Input

输入第一行是一个整数T,表示有T(T<=20)组测试数据。接下来每一组测试数据包括两个部分。第一部分只有一行,有两个整数n,m(2<=n<=1000,m<=n*(n-1)/2)。分别表示学生的人数和老师掌握的学生之间熟悉关系个数。第二部分有m行,每行有两个整数a,b。表示学生a和学生b相互认识,即有可能联合起来作弊。a和b分别表示学生的标号,且从1开始(1<=a,b<=n)。

Output

对于每组测试数据,输出按照样例的格式。第一行表示是第几组数据。如果能把所有学生分在两个考场,且不可能发生作弊行为,第二行输出”Yes”,否则输出”No”。

Sample Input
1  7 6  1 2  1 3  2 4  2 5  3 6  3 7

Sample Output
Case 1:   Yes

Source
xmu
 
本以为很难的题目,原来一个hash就可以水过,唉。。。。。
#include <stdio.h>
#include <string.h>
int main()
{
 int has[1001];
 int t, n, m;
 scanf("%d", &t);
 for(int i = 1; i <= t; i++)
 {
  scanf("%d%d", &n, &m);
  int flag = 1;
  memset(has, -1, sizeof(has));
  while(m--)
  {
   int a, b;
   scanf("%d%d", &a, &b);
   if(has[a] == -1 && flag)
   {
    if(has[b] == -1)
    {
     has[a] = 0;
     has[b] = 1;
    }
    else if(has[b] == 0)
    {
     has[a] = 1;
    }
    else has[a] = 0;
   }
   else if(has[a] == 0 && flag)
   {
    if(has[b] == -1)
    {
     has[b] = 1;
    }
    else if(has[b] == 0)
    {
     flag = 0;
    }
    
   }
   else if(has[a] == 1 && flag)
   {
    if(has[b] == -1)
    {
     has[b] = 0;
    }
    else if(has[b] == 1)
    {
     flag = 0;
    }
   }
  }
  printf("Case %d:\n", i);
  if(flag)
   printf("Yes\n");
  else
   printf("No\n");
  
 }
return 0;
}
  评论这张
 
阅读(104)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017