luogu P2419 [USACO08JAN]牛大赛Cow Contest

神奇的floyd

对于每组给定的 a 和  b 可推知a相对b的大小关系,若想得到a在所有数中的排名则需满足已知n-1个这种大小关系。

若a比b大,且b比c大,可推知a比c大。

那么使用floyd,可以枚举出所有的a b c组合,若满足a比c大或上述条件(mp[a][c]|mp[a][b]&mp[b][c]),则说明a与c的大小关系已知。

跑一遍之后统计时,循环两层1到n,第一层每次维护一个tot=1,两层数若相同continue,否则tot=tot&mp[i][j],最后ans+tot即可

#include<cstdio>
#define maxn 210
using namespace std;
int mp[maxn][maxn],ans;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        mp[a][b]=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];
    for(int i=1;i<=n;i++)
    {
        int tot=1;
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            tot=tot&(mp[i][j]|mp[j][i]);
        }
        ans+=tot;
    }
    printf("%d",ans);
}
原文地址:https://www.cnblogs.com/charlesss/p/10698823.html