POJ 3660 Cow Contest(Floyd)

题目链接: kuangbin带你飞 专题四 最短路练习 H - Cow Contest

题意

n个牛进行比赛,现已知m个关系, 牛u可以胜过牛v。
问最后可以确定排名位数的有几个牛

思路

Floyd获得两两牛之间的关系,如果一个牛可以胜过a个牛,b个牛可以胜过它,那么如果a+b=n-1,他的排名就可以确定

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 109;
const int MAX = 0x3f3f3f3f;
bool v[N][N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    memset(v, 0, sizeof(v));
    for(int i=1; i<=m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        v[a][b] = 1;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            for(int k=1; k<=n; k++)
                v[k][j] |= v[k][i] & v[i][j];

    int ans = 0;
    for(int i=1; i<=n; i++)
    {
        int cnt = 0;
        for(int j=1; j<=n; j++)
        {
            if(v[j][i])
                cnt++;
            if(v[i][j])
                cnt++;
        }
        if(cnt == n-1)
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}