http://poj.org/problem?id=3660
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.
* 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
* Line 1: A single integer representing the number of cows whose ranks can be determined
5 5 4 3 4 2 3 2 1 2 2 5
2
说明
Cow 2 loses to cows 1, 3, and 4. Thus, cow 2 is no better than any of the cows 1, 3, and 4. Cow 5 loses to cow 2, so cow 2 is better than cow 5. Thus, cow 2 must be fourth, and cow 5 must be fifth. The ranks of the other cows cannot be determined.
题意：有N头牛，评以N个等级，各不相同，先给出部分牛的等级的高低关系，问最多能确定多少头牛的等级
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <queue> 8 const int INF=0x3f3f3f3f; 9 using namespace std; 10 int D[101][101]; 11 12 int main() 13 { 14 int n,m; 15 scanf("%d %d",&n,&m); 16 //输入信息 17 for(int i=1;i<=m;i++) 18 { 19 int a,b; 20 scanf("%d %d",&a,&b); 21 D[a][b]=1;//a等级大于b 22 D[b][a]=-1;//b等级小于a 23 } 24 25 //进行适当的松弛操作（使用floyed求一下传递闭包） 26 for(int k=1;k<=n;k++) 27 { 28 for(int i=1;i<=n;i++) 29 { 30 for(int g=1;g<=n;g++) 31 { 32 if(D[i][k]==1&&D[k][g]==1) 33 D[i][g]=1; 34 else if(D[i][k]==-1&&D[k][g]==-1) 35 D[i][g]=-1; 36 37 } 38 } 39 } 40 41 //统计答案 42 int ans=0; 43 for(int i=1;i<=n;i++) 44 { 45 int g; 46 for(g=1;g<=n;g++) 47 { 48 if(i!=g&&!D[i][g])//除i=g时，D[i][g]为0说明i对g无确定的关系 49 break; 50 } 51 if(g==n+1)//说明该牛对其余的牛都有确定的关系 52 ans++; 53 } 54 printf("%d\n",ans); 55 return 0; 56 }
poj-3660 Cow Contest（传递闭包floyed算法）
原文：https://www.cnblogs.com/jiamian/p/11261751.html