[kuangbin带你飞]专题四最短路练习 H - Cow Contest （floyed传递背包）

怼烎@ 2023-08-17 15:41 113阅读 0赞

# H - Cow Contest #

题目链接：[https://vjudge.net/contest/66569\#problem/H][https_vjudge.net_contest_66569_problem_H]

题目：

*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

2
    题意：给出n,m，n是n头牛，m是m对关系，a,b，在前的即为a打败了b，一开始没看懂让我们求啥，然后百度发现用到了传递闭包，有向图的传递背包算法
    其中包括了floyed传递背包算法，就是1跟2有关系，2跟3有关系，1也就跟3有关系，算这些牛中能确立多少等级关系，一旦一头牛和其他牛都存在胜负关系，
    那么就确立一个等级关系，最后for循环遍历一下就可算出几个等级关系

//
    // Created by hanyu on 2019/7/20.
    //
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int maxn=105;
    #define MAX 0x3f3f3f3f
    
    int road[maxn][maxn];
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int front,to;
        memset(road,MAX,sizeof(road));
        for(int i=1;i<=n;i++)
            road[i][i]=0;//自己和自己不成立关系
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&front,&to);
            road[front][to]=1;//单向图
            road[to][front]=-1;//反向不成立
        }
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(road[i][k]==road[k][j]&&road[i][k]!=MAX)
                    {
                        road[i][j]=road[i][k];
                    }
                }
            }
        }//Floyd 传递闭包算法
        int cnt,sum=0;
        for(int i=1;i<=n;i++)
        {
            cnt=0;
            for(int j=1;j<=n;j++)
            {
                if(i!=j&&road[i][j]!=MAX)
                {
                    cnt++;
                }//遍历每头牛和其他牛的关系
            }
            if(cnt==n-1)//如果关系达到n-1，即和自身之外的其他牛都确定了关系，则可确定等级
                sum++;
        }
        printf("%d\n",sum);
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11219248.html

[https_vjudge.net_contest_66569_problem_H]: https://vjudge.net/contest/66569#problem/H