洛谷 P2419 [USACO08JAN]Cow Contest S（最短路：floyed）

https://www.luogu.com.cn/problem/P2419

题目大意：

给定n头奶牛(1<=N<=100)，按1..N依次编号。

m轮：两两之间进行对决，赢了的排在左边，输了的排在右边。

我们想知道奶牛们编程能力的具体排名，希望能根据这些信息，推断出尽可能多的奶牛的编程能力具体排名。

输入 #1 
5 5
4 3
4 2
3 2
1 2
2 5
输出 #1 
2

一眼拓扑排序，但是拓扑实现起来应该会很麻烦，而且数据范围挺小的，所以我们可以换一种思维

• 如果A赢了B，那么AB之间连接一条边；
• 按最短路实现所有边的连接
• 如果一个点，可以由其他所有点都有直接或者间接的连接，那么就可以确定具体的排名，
• 否则不能确定具体的名次位置

对于题目给的样例一，我们可以画一个图

注意箭头指向

在这个样例中我们就可以很清晰得得出结论

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=2000020;
const int N=200200,M=2002;
LL f[M][M];
int main()
{
    cin.tie(0); cout.tie(0);ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n,m;
        cin>>n>>m;
        for(LL i=1;i<=m;i++)
        {
            LL x,y;
            cin>>x>>y;
            f[x][y]=1;//表示x到y是联通的
        }
        for(LL k=1;k<=n;k++)
        {
            for(LL i=1;i<=n;i++)
            {
                for(LL j=1;j<=n;j++)
                {
                    //如果一开始就有路，如果两条路可以连接
                    f[i][j]=f[i][j]||(f[i][k]&&f[k][j]);
                }
            }
        }
        LL ans=0;
        for(LL i=1;i<=n;i++)
        {
            LL flag=1;
            for(LL j=1;j<=n;j++)
            {
                //对于任意节点 u，如果其他所有节点到节点 u 和从节点 u 到其他所有节点的路径都是确定的，那么节点 u 的排名就是确定的。
                if(i==j) continue;
                flag=flag&&(f[i][j]||f[j][i]);
            }
            if(flag==1) ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}