本文共 1895 字,大约阅读时间需要 6 分钟。
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
Output
Sample Input
5 5
4 3 4 2 3 2 1 2 2 5 Sample Output2
输入a,b,表示a能打败b,给出多组这种数据,求能够确定能力排行的牛有多少个。
能够确定排行,说明这个牛一定有直接或间接和其他牛比过赛,那么对于每个点,这个点之前与之连接的点和之后与之连接的点加起来,个数为n-1就能够确定绝对顺序#include#include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f#define MAXN 5005#define mod 1000000007using namespace std;int n,m;int map[MAXN][MAXN];void Floyd(){ int i,j,k; for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j];}int main(){ scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) map[i][j]=(i==j?0:INF); //注意自身和自身距离为0。 int a,b; while(m--) { scanf("%d%d",&a,&b); map[a][b]=1; } Floyd(); int ans=0; for(int i=1;i<=n;++i) { int tmp=0; for(int j=1;j<=n;++j) { if(i!=j) { if(map[i][j]
转载地址:http://nscvb.baihongyu.com/