当前位置：网站首页>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.
边栏推荐
- 【Unity3D】2D动画
- 21天学习挑战赛--第四天打卡（横竖屏切换）
- 三面（技术 +HR 面试）网易，分享我的面试经验！（已拿 offer）
- 以技术创新加速国家“碳中和”建设进程，华为云创新中心助力欣冠精密实现云智控“气”
- Qt 5.12 LTS 部署
- 超多AI开发者等你来玩转，一起燃动昇腾AI创享日南京站！
- Environment: Flink version: 1.15.1 jar package: flink-sql-connector-oracle
- Paper sharing: "FED BN" uses the LOCAL BATCH NORMALIZATION method to solve the Non-iid problem
- ebook下载 | 《 企业高管IT战略指南——企业为何要落地DevOps》
- MQTT X Web：在线的 MQTT 5.0 客户端工具
猜你喜欢
ebook下载 | 《 企业高管IT战略指南——企业为何要落地DevOps》
![[] free column Android run Android, her - as command of safety](/img/d5/771802eb57f24c1cf88657f5c5a724.png)
[] free column Android run Android, her - as command of safety
![[Free Column] Android Fragment Injection for Android Security](/img/bf/244e7095ce010bfea799d02395b419.png)
[Free Column] Android Fragment Injection for Android Security
一些自动化测试01
golang单元测试：testing包的基本使用
JMeter压测时如何在达到给定错误数量后停止测试
《痞子衡嵌入式半月刊》 第 60 期
![[免费专栏] Android安全之GDB动态调试APP](/img/e3/fd096ec64f682348cca9bbab1ec5bb.png)
[免费专栏] Android安全之GDB动态调试APP
没有 accept，TCP 连接可以建立成功吗？
华为云全流程护航《流浪方舟》破竹首发，打造口碑爆款
随机推荐
基于CC2530 E18-MS1-PCB Zigbee DIY作品
MYSQL物理存储文件的页和INNOBUF的页是否有大小区别?
21天学习挑战赛--第四天打卡（横竖屏切换）
C＃/VB.NET：从PowerPoint文档中提取文本和图片
ebook下载 | 《 企业高管IT战略指南——企业为何要落地DevOps》
毕昇编译器优化：Lazy Code Motion
有文章说明或者证明MYSQL 嵌套子查询不足之处吗?
Swift--多条件排序
华为云全流程护航《流浪方舟》破竹首发，打造口碑爆款
工大科雅深交所上市：市值45亿 齐承英家族是大股东
基于设计稿识别的可视化低代码系统实践
三面（技术 +HR 面试）网易，分享我的面试经验！（已拿 offer）
网络安全：常见的网络协议
Open Source Summer | List Details Display Based on Ruoyi Architecture
MySQL备份与恢复
leetcode 503.下一个更大元素II 单调栈
智驾科技完成C1轮融资，此前2轮已融4.5亿元
Why is the data of maxcompute garbled when imported into mysql?The table of mysql is the encoding of udf8mb4
单片机编程-状态机
[免费专栏] Android安全之Root检测和绕过(浅析)