当前位置：网站首页>hdu 2094 产生冠军(STL map || 拓扑 || STL set)

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

2022-08-09 18:35:00 【51CTO】


题目： ​ ​http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23626​​

Description

有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。
球赛的规则如下：
如果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 <iostream>
       
       

       
       #include <cstdio>
       
       

       
       #include <algorithm>
       
       

       
       #include <map>
       
       

       
       #include <string>
       
       

       
       #include <cstring>
       
       

       
       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<<v<<" "<<indegree[v]<<endl;
       
       
}
       
       

       
       map
       
       <
       
       string, 
       
       int
       
       > 
       
       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<<mp[s1]<<" "<<mp[s2]<<endl;
       
       
             
       
       addedge(
       
       mp[
       
       s1],
       
       mp[
       
       s2]);
       
       
         }
       
       
         
       
       //for(int i=1;i<top;i++)cout<<i<<" "<<indegree[i]<<endl;
       
       
         
       
       sort(
       
       indegree
       
       +
       
       1,
       
       indegree
       
       +
       
       1
       
       +
       
       top);
       
       
         
       
       if(
       
       indegree[
       
       1]
       
       ==
       
       0 
       
       && 
       
       indegree[
       
       2]
       
       !=
       
       0 ) 
       
       printf(
       
       "Yes\n");
       
       
         
       
       else 
       
       puts(
       
       "No");
       
       
    }
       
       
    
       
       return 
       
       0;
       
       
}
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    • 
       
       
  • 25.
    • 
       
       
  • 26.
    • 
       
       
  • 27.
    • 
       
       
  • 28.
    • 
       
       
  • 29.
    • 
       
       
  • 30.
    • 
       
       
  • 31.
    • 
       
       
  • 32.
    • 
       
       
  • 33.
    • 
       
       
  • 34.
    • 
       
       
  • 35.
    • 
       
       
  • 36.
    • 
       
       
  • 37.
    • 
       
       
  • 38.
    • 
       
       
  • 39.
    • 
       
       
  • 40.
    • 
       
       
  • 41.
    • 
       
       
  • 42.
    • 
       
       
  • 43.
    • 
       
       
  • 44.
    • 
       
       
  • 45.
    • 
       
       
  • 46.
    • 
       
       
  • 47.
    • 
       
       
  • 48.
    • 
       
       
  • 49.
    • 
       
       
  • 50.
    •


比如这份测试用例：


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<char*，int>更是不对。转念一想，把map放在主函数里不就能只在单个例子利用他的记忆吗！


AC：


      
      

       
       #include <iostream>
       
       

       
       #include <cstdio>
       
       

       
       #include <algorithm>
       
       

       
       #include <map>
       
       

       
       #include <string>
       
       

       
       #include <cstring>
       
       

       
       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
       
       <
       
       string, 
       
       int
       
       > 
       
       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;
       
       
}
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    • 
       
       
  • 25.
    • 
       
       
  • 26.
    • 
       
       
  • 27.
    • 
       
       
  • 28.
    • 
       
       
  • 29.
    • 
       
       
  • 30.
    • 
       
       
  • 31.
    • 
       
       
  • 32.
    • 
       
       
  • 33.
    • 
       
       
  • 34.
    • 
       
       
  • 35.
    • 
       
       
  • 36.
    • 
       
       
  • 37.
    • 
       
       
  • 38.
    • 
       
       
  • 39.
    • 
       
       
  • 40.
    • 
       
       
  • 41.
    • 
       
       
  • 42.
    • 
       
       
  • 43.
    • 
       
       
  • 44.
    • 
       
       
  • 45.
    • 
       
       
  • 46.
    • 
       
       
  • 47.
    •

代码还能优化的。


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


      
      

       
       #include <iostream>
       
       

       
       #include <cstdio>
       
       

       
       #include <algorithm>
       
       

       
       #include <cstring>
       
       

       
       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;
       
       
}
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    • 
       
       
  • 25.
    • 
       
       
  • 26.
    • 
       
       
  • 27.
    • 
       
       
  • 28.
    • 
       
       
  • 29.
    • 
       
       
  • 30.
    • 
       
       
  • 31.
    • 
       
       
  • 32.
    • 
       
       
  • 33.
    • 
       
       
  • 34.
    • 
       
       
  • 35.
    • 
       
       
  • 36.
    • 
       
       
  • 37.
    • 
       
       
  • 38.
    • 
       
       
  • 39.
    • 
       
       
  • 40.
    • 
       
       
  • 41.
    • 
       
       
  • 42.
    • 
       
       
  • 43.
    • 
       
       
  • 44.
    • 
       
       
  • 45.
    •

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


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

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


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


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


      
      

       
       #include <iostream>
       
       

       
       #include <cstdio>
       
       

       
       #include <set>
       
       

       
       #include <string>
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       const 
       
       int 
       
       maxn
       
       =
       
       2010;   
       
       

       
       int 
       
       n;
       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       //freopen("cin.txt","r",stdin);
       
       
    
       
       while(
       
       cin
       
       >>
       
       n
       
       &&
       
       n){
       
       
         
       
       int 
       
       top
       
       =
       
       1;
       
       
         
       
       set
       
       <
       
       string
       
       > 
       
       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;
       
       
}
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    • 
       
       
  • 25.
    •






原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15746559/5560567

边栏推荐

猜你喜欢

随机推荐