对于一个能够确定名次的点，可以注意到，对于该点，入度和出度的数量加起来等于N-1
（这样还是不够准确的
确切的说是，能够到达这个点的数量和这个点能够到达的数量的和
floyd不仅可以求两个点之间的最短路径，还能求两个点彼此是否能够相互到达
最后对于一个可以确定名次的点，能够到达的所有的点 加上 能够到达该点的所有点的和必须等于n-1
当然，我们可以通过二进制来简化这个过程
最后处理结果时，设一个变量flag, 因为该点能够到达本身，flag初值赋为1
对于两个点i, j首先f[i][j] | f[j][i]
因为对于这两个点，无论从j到i或是从i到j，都需算上。
同时用flag与f[i][j] | f[j][i]相&
按位与的操作是两位全为1，则得到的值为1，也就是说，若有任何一点不能到达此点或是由此点到达，我们就无法求出该点的名次
最后我们用计数器ans累加flag的值即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 150; 4 int n, m, ans = 0; 5 int f[maxn][maxn]; 6 7 inline int read() { 8 int x = 0, y = 1; 9 char ch= getchar(); 10 while(!isdigit(ch)) { 11 if(ch == ‘-‘) y = -1; 12 ch = getchar(); 13 } 14 while(isdigit(ch)) { 15 x = (x << 1) + (x << 3) + ch - ‘0‘; 16 ch = getchar(); 17 } 18 return x * y; 19 } 20 21 int main() { 22 n = read(), m = read(); 23 for(int i = 1; i <= m; ++i) { 24 int x, y; 25 x = read(), y = read(); 26 f[x][y] = 1; 27 } 28 for(int k = 1; k <= n; ++k)//floyd求两个点能否互相到达 29 for(int i = 1; i <= n; ++i) 30 for(int j = 1; j <= n; ++j) 31 f[i][j] |= f[i][k] & f[k][j]; 32 for(int i = 1; i <= n; ++i) { 33 int flag = 1;//判断i点是否能够求出具体的名次 34 for(int j = 1; j <= n; ++j) { 35 if(i == j) continue; 36 else flag &= f[i][j] | f[j][i]; 37 } 38 ans += flag;//统计答案 39 } 40 cout << ans << ‘\n‘; 41 return 0; 42 }
洛谷P2419 [USACO08JAN]牛大赛Cow Contest
原文：https://www.cnblogs.com/ywjblog/p/9382164.html
