洛谷题单指南-最短路-P2419 [USACO08JAN] Cow Contest S

原题链接：https://www.luogu.com.cn/problem/P2419

题意解读：已知n头奶牛的m场比赛的胜负关系，问有多少奶牛可以唯一确定排名。

解题思路：

1、建模

要确定一头奶牛的排名，必须满足这头奶牛与其他所有奶牛都有明确的胜负关系

胜负关系有两种：胜、负

胜可以直接胜也可以间接胜，同理负可以直接负也可以间接负

因此，该题是一个传递闭包问题，定义g[i][j] = 1表示i可以胜j，g[i][j] = 0表示i不能胜j

根据m场比赛的胜负关系，即可建图。

2、算法

要求出所有牛奶之间的传递闭包（直接或间接的胜负关系），可以采用Floyd算法：https://www.cnblogs.com/jcwy/p/18808006

然后，枚举每一个奶牛i，如果i能胜的奶牛数加上能胜过i的奶牛总数为n - 1，则表示该奶头可以唯一确定排名

for(int i = 1; i <= n; i++) 
{
    int cnt = 0;
    for(int j = 1; j <= n; j++)
        if(i != j && (g[i][j] || g[j][i]）
            cnt++;
    if(cnt == n - 1) ans++;
}

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 105, M = 5005, INF = 0x3f3f3f3f;
int g[N][N];
int n, m, ans;

int main()
{
    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                g[i][j] |= g[i][k] & g[k][j];

    for(int i = 1; i <= n; i++)
    {
        int cnt = 0;
        for(int j = 1; j <= n; j++)
            if(i != j && g[i][j] || g[j][i]) cnt++;
        if(cnt == n - 1) ans++;
    }
    cout << ans;

    return 0;
}