算法实现原理
由于我们只需要确定节点对(i,j)之间是存在i->j的路径，所以，对于松弛操作可以有两种优化方式，
(1)将所有节点对之间的存在的直接连通的边权重设为1，不连通设为0。然后运行该算法，如果mp[i][j] = 1;则（i，j）之间存在一条简单路径。如果mp[i][j] = 0,则两者之间不存在路径。
(2)可以将松弛策略改为，mp[i][j] == 1|| (mp[i][k] ==1 && mp[k][j] == 1)也即是要么，i可以通过{1,2,3,,,k-1}中的部分节点到达j,要么i可以通过{1,2,3,,,k-1}中的部分节点到达j，可以参考对Floyd warshall 算法的分析。
这里需要先求一下所有牛之间的传递闭包， 那么我们这题与传递闭包又有什么关系呢。 下面将慢慢解答。
如果一头牛被x头牛打败，并且可以打败y头牛，如果x+y=n-1，则我们容易知道这头牛的排名就被确定了，所以我们只要将任一头牛，可以打败其他的牛的个数x， 和能打败该牛的牛的个数y求出来，在遍历所有牛判断一下是否满足x+y=n-1，就知道这个牛的排名是否能确定了（而传递闭包，正好将所有能得出关系都求出来了）， 再将满足这个条件的牛数目加起来就是所求解。 x可以看成是入度， y是出度。
在floyd-warshall求每对顶点间的最短路径算法中，可以通过O(v^3)的方法求出图的传递闭包。可以位每条边赋以权值1,然后运行Floyd-Wareshall。如果从 i 到 j 存在一条路径，则d(i,j)<N,否则d(i,j)=MAX。
一种改进的算法是：由于我们需要的只是判断是否从i到j存在一条通路，所以在Floyd-Wareshall中的动态规划比较中，我们可以把min和+操作改为逻辑or( || )和逻辑（&&）。也就是将 d[i][j] = min(d[i][j], d[i][k]+dist[k][j]); 改成 if(d[i][j] == 1 || (d[i][k] == 1 && d[k][j] == 1)) d[i][j] = 1;
1 #include <stdio.h> 2 #include <algorithm> 3 #include <iostream> 4 #include <stdbool.h> 5 #include <stdlib.h> 6 #include <string> 7 #include <string.h> 8 #include <math.h> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 13 #define INF 0x3f3f3f3f 14 #define LL long long 15 using namespace std; 16 const int MAXN = 1005; 17 18 19 int N,M; 20 int vis[MAXN][MAXN]; 21 22 void Floyd() 23 { 24 for (int k=1;k<=N;k++) 25 { 26 for (int i=1;i<=N;i++) 27 { 28 for (int j=1;j<=N;j++) 29 { 30 if (vis[i][j]==1 || (vis[i][k] == 1 && vis[k][j] == 1)) 31 vis[i][j] = 1; 32 } 33 } 34 } 35 } 36 37 38 int main() 39 { 40 //freopen("../in.txt","r",stdin); 41 while (~scanf("%d%d",&N,&M)) 42 { 43 memset(vis,0, sizeof(vis)); 44 while (M--) 45 { 46 int x,y; 47 scanf("%d%d",&x,&y); 48 vis[x][y] = 1; 49 } 50 Floyd(); 51 int cnt = 0; 52 int ans = 0; 53 for (int i=1;i<=N;i++) 54 { 55 cnt = 0; 56 for (int j=1;j<=N;j++) 57 { 58 if (i == j) 59 continue; 60 if (vis[i][j] == 1 || vis[j][i] == 1) 61 cnt++; 62 } 63 if (cnt == N-1) 64 ans++; 65 } 66 printf("%d ",ans); 67 } 68 return 0; 69 }