又是一年CET46(0243)

问题描述

CET46 成绩出来啦,一群学生在谈论他们的成绩。A说他的成绩比B高,B说他的成绩比C低,D说他的成绩和E一样…… 
他们当中可能有人在说谎。你的任务就是判断是否有人在说谎。 
PS: 
A < B 表示A的成绩比B低。 
A > B 表示A的成绩比B高。 
A = B 表示A的成绩和B一样。

输入

有多组数据。对于每组数据 
第一行两个整数 N和M,分别代表有N个学生(编号1—N),和已知的M个关系。(1 < N <= 200 ,0 < M < 40000) 
第二到第M+1行,每行对应一个关系。

输出

如果有人说谎输出 “Someone have told lies!”,否则输出 “Maybe they are all honest!”。

样例输入

4 3
1 < 2
1 < 3
2 > 3
3 3
1 > 2
2 > 3
3 = 1

样例输出

Maybe they are all honest!
Someone have told lies!

由于‘=’的存在,因此先用并查集合并。

额、可能想复杂了,应该有其他简单的方法。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define N 210
#define M 200200 struct les{
int a,b;
}p[M];
int tot;
int n,m;
int flag;
int f[N];
int in[N];
int vis[N];
int mpt[N][N]; void init()
{
tot=;
flag=;
for(int i=;i<=n;i++) f[i]=i;
}
int Find(int x)
{
if(x!=f[x]) f[x]=Find(f[x]);
return f[x];
}
void UN(int x,int y)
{
x=Find(x);
y=Find(y);
f[x]=y;
}
bool solve()
{
//build
int tn=;
memset(in,,sizeof(in));
memset(vis,,sizeof(vis));
memset(mpt,,sizeof(mpt));
for(int i=;i<=tot;i++){
int a=Find(p[i].a);
int b=Find(p[i].b);
if(!vis[a]) vis[a]=,tn++;
if(!vis[b]) vis[b]=,tn++;
if(!mpt[a][b]){ //重边判断
mpt[a][b]=;
in[b]++;
}
}
//work
priority_queue<int,vector<int>,greater<int> >q;
for(int i=;i<=n;i++){
if(!in[i] && vis[i]) q.push(i);
}
int cnt=;
while(!q.empty()){
int u=q.top();
q.pop();
cnt++;
for(int v=;v<=n;v++){
if(mpt[u][v] && vis[v]){
in[v]--;
if(!in[v]) q.push(v);
}
}
}
if(cnt<tn) return ;
return ;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
while(m--){
int a,b;
char c;
scanf(" %d %c %d",&a,&c,&b);
if(!flag) continue;
if(c!='='){
if(Find(a)==Find(b)) flag=;
if(c=='>') swap(a,b);
p[++tot].a=a;
p[tot].b=b;
}
else{
UN(a,b);
}
}
if(flag){
flag=solve();
if(flag) printf("Maybe they are all honest!\n");
else printf("Someone have told lies!\n");
}
else
printf("Someone have told lies!\n");
}
return ;
}

最新文章

  1. 怎么解决tomcat占用8080端口问题
  2. 用DropBox分享Unity3D的Web应用
  3. 破解版windows 7(旗舰版)下安装并使用vagrant统一开发环境
  4. javascript学习面向对象(二)
  5. HDU 1312 (BFS搜索模板题)
  6. android之Itent.ACTION_PICK Intent.ACTION_GET_CONTENT妙用
  7. 第一篇:GCD多线程的概念
  8. IPv6-only 的兼容性解决方案
  9. SQL点滴32—Excel中CONCATENATE函数生成SQL语句
  10. Unable to find setter method for attribute: 属性名
  11. CSS之 float 属性
  12. oracle数据库管理系统常见的错误(一)
  13. 使用ASP.NET Core开发GraphQL服务器 -- 预备知识(下)
  14. mysql 索引中的USING BTREE 的意义
  15. C语言第01次作业--顺序、分支结构
  16. element ui 手动关闭$notify弹框
  17. zsh快捷键
  18. back
  19. for..in 遍历js对象
  20. iOS-通讯录(无界面)

热门文章

  1. 面向对象Part2
  2. ios中的http:get,post,同步,异步
  3. CRM域用户误删恢复
  4. Ubuntu 16.04 LTS Final Beta
  5. PYTHON ASYNCIO: FUTURE, TASK AND THE EVENT LOOP
  6. Ibatis 异常:Unable to open connection to &quot;oledb , provider V2.0.0.0 in framework .NET V2.0&quot;.
  7. 子句判断、启动强度和去模糊化--AForge.NET框架的使用(三)
  8. 在Android中自动实现横竖屏切换的问题
  9. Python 实现的随机森林
  10. iOS钉钉远程打卡助手(支持越狱和非越狱)
  11. [BZOJ4804]欧拉心算
  12. &lt;&lt;精通iOS开发&gt;&gt;第14章例子代码小缺陷的修复
  13. 【转载】Session的生命周期
  14. Flask 蓝图,数据库链接
  15. (一)七种AOP实现方法
  16. jmeter接口测试基础知识2.0
  17. luogu P2000 拯救世界
  18. 提升linux下TCP服务器并发连接数(limit)
  19. VS Code 使用小技巧
  20. kafka 基础知识梳理