poj-3660---Cow Contest

我会带着你远行 2022-05-26 08:14 56阅读 0赞

Cow Contest

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>14435</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;8083</td> 
  </tr> 
 </tbody> 
</table>

Description

*N* (1 ≤ *N* ≤ 100) cows, conveniently numbered 1..*N*, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow *A* has a greater skill level than cow *B* (1 ≤ *A* ≤ *N*; 1 ≤ *B* ≤ *N*; *A* ≠ *B*), then cow *A* will always beat cow *B*.

Farmer John is trying to rank the cows by skill level. Given a list the results of *M* (1 ≤ *M* ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

Input

\* Line 1: Two space-separated integers: *N* and *M*  
\* Lines 2..*M*\+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, *A*, is the winner) of a single round of competition: *A* and *B*

Output

\* Line 1: A single integer representing the number of cows whose ranks can be determined

Sample Input

5 5
    4 3
    4 2
    3 2
    1 2
    2 5

Sample Output

Source

[USACO 2008 January Silver][]

题目大意：题意很简单，就是给牛确定排名关系，给出n条牛，以及m个比赛状况：A:B谁在前谁就赢，问最后有多少头牛的排名关系是确定的

思路：上来我是没有思路的，然后想了一会，突然想到把赢的一方都用1初始化，然后输的都用-1初始化，然还是没用，最后百度了代码，发现用到什么传递闭包…………

传递闭包：

所谓传递性，可以这样理解：对于一个节点i，如果j能到i，i能到k，那么j就能到k。求传递闭包，就是把图中所有满足这样传递性的节点都弄出来，计算完成后，我们也就知道任意两个节点之间是否相连。   
传递闭包的计算过程一般可以用Warshell算法描述：   
For 每个节点i Do   
    For 每个节点j Do   
    If j能到i Then   
        For 每个节点k Do   
        a\[j, k\] := a\[j, k\] Or ( a\[j, i\] And a\[ i, k\] )   
其中a数组为布尔数组，用来描述两个节点是否相连，可以看做一个无权图的邻接矩阵。可以看到，算法过程跟Floyd很相似，三重循环，枚举每个中间节点。只不过传递闭包只需要求出两个节点是否相连，而不用求其间的最短路径长。

一头牛的等级，当且仅当它与其它N-1头牛的关系确定时确定，于是我们可以将牛的等级关系看做一张图，然后进行适当的松弛操作，得到任意两点的关系，再对每一头牛进行检查即可

代码：

#include<queue>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll long long
    #define inf 99999999
    #define N 111
    int e[N][N];
    int dis[N];
    int book[N];
    int m,n;
    
    int main()
    {
        scanf("%d%d",&n,&m);
    
           memset(e,0,sizeof(e));//初始化为0
            int i,j,a,b,c,ans=0,k=0;
            for(i=1; i<=m; i++)
            {
                scanf("%d%d",&a,&b);
                e[a][b]=1;//初始化，a赢b
                e[b][a]=-1;//b输a;
            }
            for(k=1; k<=n; k++)
            {
                for(i=1; i<=n; i++)
                {
                    for(j=1; j<=n; j++)
                    {
                        if( e[i][k]==e[k][j]&&(e[i][k]==1||e[i][k] == -1 ) )
                            e[i][j]=e[i][k];
                    }
                }
            }
    //        for(i=0;i<=n;i++)
    //        {
    //            for(j=1;j<=n;j++)
    //                printf("%10d ",e[i][j]);
    //            printf("\n");
    //        }
            for(i=1;i<=n;i++)
            {
                int sum=0;
                for(j=1;j<=n;j++)
                {
                    if(e[i][j])
                        sum++;
                }
                if(sum==n-1)//与剩下的n-1头牛的胜负关系确定
                    ans++;
            }
            printf("%d\n",ans);
    
        return 0;
    }

[USACO 2008 January Silver]: http://poj.org/searchproblem?field=source&key=USACO+2008+January+Silver