Cow Contest
Time Limit: 1000MS |
|
Memory Limit: 65536K |
Total Submissions: 3613 |
|
Accepted: 1911 |
Description
N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.
The contest is conducted in several head-to-head rounds, each between two cows. If cowA has a greater skill level than cow
B (1 ≤ A ≤ N; 1 ≤B ≤ N; A ≠
B), then cow A will always beat cowB.
Farmer John is trying to rank the cows by skill level. Given a list the results ofM (1 ≤
M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer,A, is the winner) of a single round of competition:
A and B
Output
* Line 1: A single integer representing the number of cows whose ranks can be determined
Sample Input
5 5
4 3
4 2
3 2
1 2
2 5
Sample Output
2
Source
这道题的题题意很明了
给定n位大牛,然后在给出他们的m个关系,(关系是A强于B)
然后输出能够确定能力排名的大牛个数
解释一下样例:
按照题目所叙述可以画出一个网络图(路径就用A->B的单向路线)可以确定5是最弱的,而且还可以看到2只比5更强,所以倒数一二名是可以确定的,但是另外三个点,我们只知道4比3要强,但是不知道4和1的强弱关系,同理3和1也无法判断,所以样例输出2
我的思路:
这道题我写的很顺利,大概花了不到20分钟就AC了。。。用的是floyd算法
我们首先观察到数据规模比较小是100的,所以100^3是可以满足题意的,我们先用floyd算法求出最短路的矩阵path[i][j],然后通过这个矩阵依次判断每一个点A是否存在有和他完全没有关系的点即是说path[a][b]==-1且path[b][a]==-1,最后统计这种点的数量用n减去就可以了
我的代码;
分享到:
相关推荐
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
poj1087贪心算法实验报告 poj1087贪心算法实验报告
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
北大POJ2240-Arbitrage【Floyd】 解题报告+AC代码
北大POJ2253-Frogger【Floyd】 解题报告+AC代码
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
供初学编程基本算法的人练习使用,在poj.grids.cn上
POJ各题算法分类和题目推荐.pdf
北大POJ1125-Stockbroker Grapevine【Floyd】 解题报告+AC代码
关于C++ 算法 北大网站POJ 八数码问题
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
北大POJ中级-基本算法 解题报告+AC代码
用贪心算法解决POJ 1065的木棍处理问题
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类