hdu 2094 产生冠军(STL map || 拓扑 || STL set)

网友投稿 648 2022-08-27

hdu 2094 产生冠军(STL map || 拓扑 || STL set)

hdu 2094 产生冠军(STL map || 拓扑 || STL set)

题目: ​​ 球赛的规则如下: 如果A打败了B,B又打败了C,而A与C之间没有进行过比赛,那么就认定,A一定能打败C。 如果A打败了B,B又打败了C,而且,C又打败了A,那么A、B、C三者都不可能成为冠军。 根据这个规则,无需循环较量,或许就能确定冠军。你的任务就是面对一群比赛选手,在经过了若干场撕杀之后,确定是否已经实际上产生了冠军。

Input

输入含有一些选手群,每群选手都以一个整数n(n<1000)开头,后跟n对选手的比赛结果,比赛结果以一对选手名字(中间隔一空格)表示,前者战胜后者。如果n为0,则表示输入结束。

Output

对于每个选手群,若你判断出产生了冠军,则在一行中输出“Yes”,否则在一行中输出“No”。

Sample Input

3 Alice Bob Smith John Alice Smith 5 a c c d d e b e a d 0

Sample Output

Yes No

原来我是这样想的:只要只有一个入度是0的点那么就有唯一的冠军。于是愉快的敲完代码,测试完用例没有发现错误交上去结果不断的WA。。后来我发现问题出现在我使用的map上:

WA:

#include #include #include #include #include #include using namespace std;const int maxn=2010;int indegree[maxn],head[maxn],ip;int n;struct node{ int v,next;}edge[maxn];void init(){ ip=0; memset(indegree,0,sizeof(indegree));}void addedge(int u,int v){ edge[ip].v=v; edge[ip].next=head[u]; head[u]=ip++; indegree[v]++; //cout< mp;int main(){ //freopen("cin.txt","r",stdin); while(cin>>n&&n){ init(); int top=0; for(int i=1;i<=n;i++){ string s1,s2; cin>>s1>>s2; if(!mp[s1]){ mp[s1]=++top; } if(!mp[s2]){ mp[s2]=++top; } //cout<

比如这份测试用例:

5

a c

c d

d e

b e

a d

4

aa bb

bb cc

cc aa

dd aa

4

a b

b c

c a

d a

第二个例子和第三个例子应该是一样的结果,但运行出来不对。因为第一个例子对第三个例子造成了“数据污染”。前面已经输入过a,b,c,d后面接着输入,mp[s1],mp[s2]的默认值不是0!单个例子我利用了map的“记忆”,可是多个例子它的记忆又导致了错误的产生。真是一把双刃剑。而用map更是不对。转念一想,把map放在主函数里不就能只在单个例子利用他的记忆吗!

AC:

#include #include #include #include #include #include using namespace std;const int maxn=2010;int indegree[maxn],head[maxn],ip;int n;struct node{ int v,next;}edge[maxn];void init(){ ip=0; memset(indegree,0,sizeof(indegree));}void addedge(int u,int v){ edge[ip].v=v; edge[ip].next=head[u]; head[u]=ip++; indegree[v]++;}int main(){ //freopen("cin.txt","r",stdin); while(cin>>n&&n){ init(); int top=0; map mp; for(int i=1;i<=n;i++){ string s1,s2; cin>>s1>>s2; if(!mp[s1]){ mp[s1]=++top; } if(!mp[s2]){ mp[s2]=++top; } addedge(mp[s1],mp[s2]); } sort(indegree+1,indegree+1+top); if(indegree[1]==0 && indegree[2]!=0 ) printf("Yes\n"); else puts("No"); } return 0;}

代码还能优化的。

不依赖于STL了。自己写函数联系字符串和数字:

#include #include #include #include using namespace std;const int maxn=2010;int indegree[maxn],ip;int n;char name[maxn][20];int name_count;void init(){ ip=0; name_count=0; memset(indegree,0,sizeof(indegree)); memset(name,0,sizeof(name));}int namedex(char s[]){ int i; for(i=1;i<=name_count;i++){ if(strcmp(s,name[i])==0) { return i; } } if(i>name_count) strcpy(name[++name_count],s); return name_count;}int main(){ //freopen("cin.txt","r",stdin); while(cin>>n&&n){ init(); for(int i=1;i<=n;i++){ char s[20]; cin>>s; int a=namedex(s); cin>>s; int b=namedex(s); indegree[b]++; } sort(indegree+1,indegree+1+name_count); if(indegree[1]==0 && indegree[2]!=0 ) printf("Yes\n"); else puts("No"); } return 0;}

开始做这题很不顺的,有几个点:最开始认为图里存在子环是不可以的,后来才知道只要环不是连起所有元素的大环就可以。

比如上面的右边图,d能打败a,那么也间接的打败了b,c。所以d是冠军。

我也看了看其他大神的思路,有这样的解法(很妙~):输的人数比所有人数少1则有一个人没有输,他就是唯一的冠军。这得用好set。

#include #include #include #include using namespace std;const int maxn=2010; int n;int main(){ //freopen("cin.txt","r",stdin); while(cin>>n&&n){ int top=1; set mp,key; for(int i=1;i<=n;i++){ string s1,s2; cin>>s1>>s2; mp.insert(s1); mp.insert(s2); key.insert(s2); } if(mp.size()-key.size()==1) printf("Yes\n"); else puts("No"); } return 0;}

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:hdu 2608 0 or 1(数论推理)
下一篇:你最深爱的编程语言其实很烂
相关文章

 发表评论

暂时没有评论,来抢沙发吧~