当前位置：网站首页>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.
开始做这题很不顺的，有几个点：最开始认为图里存在子环是不可以的，后来才知道只要环不是连起所有元素的大环就可以。
比如上面的右边图，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.
边栏推荐
猜你喜欢
论文精读：VIT - AN IMAGE IS WORTH 16X16 WORDS: TRANSFORMERS FOR IMAGE RECOGNITION AT SCALE
【Unity3D】2D动画
![[Free column] Xposed plug-in development for Android security [from scratch] tutorial](/img/7b/a036ac664c7e27ed7d87e7ee18c05d.png)
[Free column] Xposed plug-in development for Android security [from scratch] tutorial
![[Free Column] Android Fragment Injection for Android Security](/img/bf/244e7095ce010bfea799d02395b419.png)
[Free Column] Android Fragment Injection for Android Security
单片机编程-状态机
史上最全架构师知识图谱（纯干货）
字节二面，差点倒在了MySQL上面
mysql 重复数据 分组 多条最新的记录
2022深圳(软考高级)信息系统项目管理师认证报名
YOLO v3源码详解
随机推荐
[免费专栏] Android安全之安卓APK浅析
Mysql table structure change scheme comparison and analysis
Tims中国上市进入倒计时：年亏3.8亿 估值降至14亿美元
[免费专栏] Android安全之Android应用的汉化功能(修改so中的字符串内容)
渗透测试——CFS三层靶机内网渗透实操
视频是主动学习吗？
Go-Excelize API源码阅读（五）—— Close()
winpe工具WEPE微PE工具箱
YOLO v3源码详解
Detailed explanation of VIT transformer
Codesys结构变量编程应用(STRUCT类型)
2022.08.05_每日一题
2022.08.06_每日一题
《痞子衡嵌入式半月刊》 第 60 期
国产抗新冠口服药每瓶不超300元/ 我国IPv6网络全面建成/ 谷歌入局折叠屏手机...今日更多新鲜事在此...
16 张图解 ｜ 淘宝 10年架构演进
Iptables防火墙常见的典型应用场景
Openharmony轻量系统实验--GPIO点灯
基于CC2530 E18-MS1-PCB Zigbee DIY作品
Bi Sheng Compiler Optimization: Lazy Code Motion