P2419 [USACO08JAN]牛大赛Cow Contest

Floyd不仅可以算最短路,还可以处理点之间的关系。

跑一遍Floyd,处理出每个点之间是否有直接或间接的关系。

如果某个点和其他$n-1$个点都有关系,那么它的排名就是可确定的。

 #include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
int n,m,d[][],ans;
int main(){
scanf("%d%d",&n,&m); int q1,q2;
for(re int i=;i<=m;++i) scanf("%d%d",&q1,&q2),d[q1][q2]=;
for(re int k=;k<=n;++k)
for(re int j=;j<=n;++j)
for(re int i=;i<=n;++i)
d[i][j]|=d[i][k]&d[k][j];//(i,k),(k,j)都要有关系,(i,j)才有关系
for(re int i=;i<=n;++i){
int tmp=;
for(re int j=;j<=n;++j)
if(i!=j) tmp&=d[i][j]|d[j][i];//是否与其他n-1个点都有关系
ans+=tmp;
}printf("%d",ans);
return ;
}
05-11 16:56
查看更多