[洛谷 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注