Cow Contest—poj3660

程序员玉航技术 2022年11月8日

0 收藏 514 点赞 1,916 浏览 811 个字

题意：有n头牛，m个关系，a b意思是a能打败b；求能确定排名的有几个；

如果一头牛被x头牛打败，并且可以打败y头牛，如果x+y=n-1，则我们容易知道这头牛的排名就被确定了，所以我们只要将任一头牛，可以打败其他的牛的个数x，和能打败该牛的牛的个数y求出来，在遍历所有牛判断一下是否满足x+y=n-1，就知道这个牛的排名是否能确定了（而传递闭包，正好将所有能得出关系都求出来了）

传递闭包就是如果a>b,b>c那么a>c;

 #include<iostream>
 #include<stdio.h>
 #include<math.h>
 #include<string.h>
 #include<algorithm>
 #define INF 0xfffffff
 #define N 1100
 using namespace std; int n,m;
 int maps[N][N]; void Floyd()
 {
     int i,j,k;
     for(k=;k<=n;k++)
         for(i=;i<=n;i++)
             for(j=;j<=n;j++)
                 if(maps[i][k]==&&maps[k][j]==)
                     maps[i][j]=;
 } int main()
 {
     int i,j,a,b;
     while(scanf("%d%d",&n,&m)!=EOF)
     {         for(i=;i<=n;i++)
             for(j=;j<=n;j++)
                 maps[i][j]=;         for(i=;i<m;i++)
         {
             scanf("%d%d",&a,&b);
             maps[a][b]=;
         }         Floyd();         int ans=;
         for(i=;i<=n;i++)
         {
             int k=;
             for(j=;j<=n;j++)
             {
                 if(i==j)continue;                 if(maps[i][j]==||maps[j][i]==)
                     k++;
             }
             if(k==n-)
                 ans++;
         }
         printf("%d\n",ans);
     }
     return ;
 }