又是一年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=0; flag=1; for(int i=1;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=0; memset(in,0,sizeof(in)); memset(vis,0,sizeof(vis)); memset(mpt,0,sizeof(mpt)); for(int i=1;i<=tot;i++){ int a=Find(p[i].a); int b=Find(p[i].b); if(!vis[a]) vis[a]=1,tn++; if(!vis[b]) vis[b]=1,tn++; if(!mpt[a][b]){ //重边判断 mpt[a][b]=1; in[b]++; } } //work priority_queue<int,vector<int>,greater<int> >q; for(int i=1;i<=n;i++){ if(!in[i] && vis[i]) q.push(i); } int cnt=0; while(!q.empty()){ int u=q.top(); q.pop(); cnt++; for(int v=1;v<=n;v++){ if(mpt[u][v] && vis[v]){ in[v]--; if(!in[v]) q.push(v); } } } if(cnt<tn) return 0; return 1; } 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=0; 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! "); else printf("Someone have told lies! "); } else printf("Someone have told lies! "); } return 0; }