Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 7104 | Accepted: 3921 |
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 cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.
Farmer John is trying to rank the cows by skill level. Given a list the results of M (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
题意:
给出 n(1 ~ 100) 和 m(1 ~ 4500),代表有 n 个结点还有 m 个关系。后给出 m 条关系,每次给出 a 和 b,代表 a > b。问根据这些关系,能最终确定排名的一共有多少个节点。
思路:
Floyd 传递闭包。如果这个结点能确定出第几,说明经过 Floyd 闭包后,与其他每个结点都会有一个确定的关系,要不就是 你大于我,要不就是 我大于你,如果 Map [ i ] [ j ] 和 Map [ j ] [ i ] 都为 0 ,说明两者之间的关系还没有确定。那么这个点就不能确定出第几名。所以最终判断有多少个结点满足与除了自己外的所有点都有 Map [ i ] [ j ] || Map [ j ] [ i ] 的即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int Map[105][105]; int n; void floyd () { for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (Map[i][k] && Map[k][j]) Map[i][j] = 1; } } } } int main() { int m; while (~scanf("%d%d", &n, &m) && (n + m)) { memset(Map, 0, sizeof(Map)); while (m--) { int a, b; scanf("%d%d", &a, &b); Map[a][b] = 1; } floyd(); int ans = 0; for (int i = 1; i <= n; ++i) { int j; for (j = 1; j <= n; ++j) { if (i == j) continue; if (!Map[i][j] && !Map[j][i]) break; } if (j == n + 1) ++ans; } printf("%d\n", ans); } }
相关推荐
有n头牛比赛,m种比赛结果,最后问你一共有多少头牛的排名被确定了,其中如果a战胜b,b战胜c,则也可以说a战胜c,即可以传递胜负。这样如果一头牛的被x头牛打败,打败y头牛,且x+y=n-1,则我们容易知道这头牛的排名...
Ulm Local Contest1996-1999
maa-the-Contest-Problem-book
Turn theory into practice by entering COMAP's Mathematical Contest in Modeling (MCM). The study of mathematics as a subject in its own right may have started with Pythagoras, but people have been ...
UCF Local Contest — September 5, 2015 UCF Local Contest — September 5, 2015 UCF Local Contest — September 5, 2015
DPA Contest V2相关情况简介~
ACM International Collegiate Programming Contest 2000/2001 Mid-Central European Regional Contest
Andrew Stankevich Contest 45 Problem analysis, cf
2008 Benelux Algorithm Programming Contest.rar 包含题目、测试数据、解答
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
国际大学生程序设计竞赛
2013 ACM ICPC Southeast USA Regional Programming Contest 原题
这是08年D类样题仅供大家备考使用2008 National English Contest for College Students (Level D) (Sample)
2008 ACM ICPC South Central USA Regional Programming Contest
2014 Multi-University Training Contest 3(标程)
Southeastern European Regional Programming Contest 2007 测试数据供大家在纠结之时调试的神器
2014 Multi-University Training Contest 2标程加数据 除1011题
有2019 Multi-University Training Contest 10的数据和标程,欢迎下载
tencent innovation contest title of test
我在我们学院上做的,有600人访问,带注册登陆,后台,答题,排名。后台密码:mylhei@bhu!演示网址:contest.bhucx.cn