【POJ】3660 Cow Contest

题目链接：http://poj.org/problem?id=3660

题意：n头牛比赛，有m场比赛，两两比赛，前面的就是赢家。问你能确认几头牛的名次。

题解：首先介绍个东西，传递闭包，它可以确定尽可能多的元素之间的关系。

然后回到这道题，怎么能确认这头牛的名次，也就是不管它胜还是败都能推导出其他n-1头牛跟它的关系。具体思想看代码。QWQ

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int maxn = ;

 const int inf = 1e9;

 int n,m;

 int mp[maxn][maxn];

 void floyd(){

     for(int k = ; k <= n ; k++){

         for(int i = ; i <= n ;i++){

             for(int j = ; j <= n ;j++){

                 if(mp[i][j] ==  || (mp[i][k] ==  && mp[k][j] == ) ){

                     mp[i][j] = ;

                 }

             }

         }

     }

 }

 int main(){

     cin>>n>>m;

     for( int i = ; i <= m ;i++){

         int x,y;

         cin>>x>>y;

         mp[x][y] = ;

     }

     floyd();

     int ans = ;

     for(int i = ; i <= n ;i++){

         int cnt = ;

         for(int j = ; j <= n; j++){

             if(i == j)

                 continue;

             if(mp[i][j] ==  || mp[j][i] == ){

                 cnt++;

             }

         }

         if(cnt == n-)

             ans++;

     }

     cout<<ans<<endl;

     return ;

 }