POJ 3660 Cow Contest(Floyd传递闭包)

POJ 3660 Cow Contest(Floyd传递闭包)

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

题意:有N头牛,每个牛有一个唯一且不同的能力等级值.然后他们中的两头牛进行M场比赛,并给你这M场的比赛结果.现在的问题是问你有多少头牛可以确定自己的排名了? 如果对于a胜b且b胜c,那么肯定a胜c. 且如果已经知道了a胜的牛数目+比a厉害的牛数目正好==N-1,那么a的排名也肯定可以推出来.

分析:

首先此题我们要求的就是从a点能到达的点数目与能到达a点的点数目.这两个值,且看这两个值的和是不是==N-1.

我们用mp[i][j]=1表示从i能到j,mp[i][j]=0表示从i不能到j. 然后我们用Floyd的算法求出所有的mp关系.这样我们就可以知道对于一个特定的a点来说,mp[i][a]的值与mp[a][i]的值分别是多少了.

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100+10;
int mp[maxn][maxn];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            mp[i][j]= i==j?1:0;
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            mp[u][v]=1;
        }
        for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            mp[i][j] = mp[i][j]|(mp[i][k]&mp[k][j]);

        int degree[maxn];//此处把入度和出度合并计算了
        memset(degree,0,sizeof(degree));
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)if(i!=j)
        {
            if(mp[i][j])
            {
                ++degree[i],++degree[j];
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)if(degree[i]==n-1)
            ++ans;
        printf("%d\n",ans);
    }
    return 0;
}