[洛谷 2419,poj 3660][USACO08JAN]牛大赛Cow Contest

题目链接

https://www.luogu.org/problem/P2419

http://poj.org/problem?id=3660

题解

如果 A 能赢 B，我们可以在 A 和 B 之间连一条有向边。如果点 A 能够到达其他所有的点，那么他的排名就能够确定。

如何判断一个点可以到达其他的点呢？我们可以用 floyd 算法来解决。

事实上，求有向图中任意两点连通性的结果叫做有向图的传递闭包。

#include <stdio.h>
int f[105][105];
int main()
{
 int n,m,ans=0;
 scanf("%d%d",&n,&m);
 for(int i=1;i<=m;i++)
 {
  int a,b;
  scanf("%d%d",&a,&b);
  f[a][b]=1;
 }
 for(int k=1;k<=n;k++)
  for(int i=1;i<=n;i++)
   for(int j=1;j<=n;j++)
    f[i][j]=f[i][j]|(f[i][k]&f[k][j]);
 for(int i=1;i<=n;i++)
 {
  int res=1;
  for(int j=1;j<=n;j++)
   if(i!=j)res&=(f[i][j]|f[j][i]);
  ans+=res;
 }
 printf("%d\n",ans);
 return 0;
}