luogu P2419 [USACO08JAN]牛大赛Cow Contest

佚名 6年前 (2019-04-12) 随笔 902人围观抢沙发百度已收录

神奇的floyd

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

若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); }