题解 P2419 【[USACO08JAN]Cow Contest S】

· · 题解

一种不是拓扑排序也不是Floyd的玄学算法

目的

就拿样例来说吧：

我们其实可以从图中获得更多信息，比如1比5厉害等，所以我们希望它能把我们所有的已知信息都表现出来，像这样：

然后就可以方便地做判断了：哪个点的入度和出度之和 =n-1 ，哪个点就可以确定排名。 在实际应用中，我们为了方便，再把每个点都和自己连一条边（反正不用任何图论算法，连了也没关系），就可以直接判断哪个点的入度和出度之和 =n 了。

具体方法

先用矩阵存图，1指向2就把第一行第二列变成1，以此类推，得到：

然后要变成第二张图的样子（把所有已知信息表示出来），具体步骤： 如果(x,y)点有标记，(y,z)点也有标记，那么(x,z)点就可以打标记。

为什么呢？因为(x,y)点有标记表示x比y厉害，(y,z)点有标记表示y比z厉害，x比y厉害，y比z厉害，x就比z厉害，所以(x,z)点就可以打标记。

最后，要如何判断点i能否和每个点都连边呢？其实很简单：只需要把第i行和第i列上的点都加起来，再减去1（点(i,i)被计算了两次），看是否为n就行。

为什么呢？因为第i行的标记表示i比别“人”厉害，第i列的标记表示别“人”比i厉害，知道几个“人”比i厉害，几个“人”比i蒻，就可以知道i的排名了。

算法比较难理解，有耐心的话可以仔细画画想想。

附上AC代码：

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast")
#pragma GCC optimize("inline")
using namespace std;
bool a[110][110];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x][y]=1;
    }
    for(int i=1;i<=n;i++)
        a[i][i]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j])
            {
                for(int k=1;k<=n;k++)
                    if(k!=i&&a[k][i])
                        a[k][j]=1;
                for(int k=1;k<=n;k++)
                    if(k!=j&&a[j][k])
                        a[i][k]=1;
            }
    int num=0;
    for(int i=1;i<=n;i++)
    {
        int ans=0;
        for(int j=1;j<=n;j++)
        {
            ans+=a[i][j];
            ans+=a[j][i];
        }
        if(ans-1==n)
            num++;
    }
    cout<<num<<endl;
    return 0;
}