题目大意:一群牛比赛,每场两只牛对打,并分出胜负,现在问你能确定几只牛的战斗力排名。
如果a>b,b>c,那么c一定小于a.用wallshall算法算出比某个元素大的元素,如果比该元素大的和比该元素小的数量为n-1,那么就可以确定排名。(即该元素可以到达任何元素)
#include#include #include #include #include #define inf 0x3f3f3fusing namespace std;int a[105][105];int main(){ int n,m; cin>>n>>m; memset(a,0,sizeof(a)); while(m--) { int x,y; cin>>x>>y; a[y][x]=1; } for(int k=1;k<=n;k++)//warshall算出传递闭包 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]||(a[i][k]&a[k][j])) a[i][j]=1; int ans=0; for(int i=1;i<=n;i++) { int g=0; for(int j=1;j<=n;j++) { if(a[i][j]) g++;//统计比i大的元素 if(a[j][i]) g++;//统计比i小的元素 } if(g==n-1) ans++; } cout< <