题目大意:给一些比赛的结果,求出能确定排名的牛的数量。
思路:关键是判断这些牛如何被确定排名,只要其他的N-1只牛可以与这个牛联通,当然这些联通路是单向的,就可以确定他的排名。
#include<cstdio> #include<iostream> const int INF=1<<28; using namespace std; int map[150][150]; int dis[150][150]; int v[150]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { int i,j,a,b; int k; int tot=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=INF; for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); map[a][b]=1; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) { dis[i][j]=map[i][j]; dis[i][i]=0; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) dis[i][j]=dis[i][j]>dis[i][k]+dis[k][j]?dis[i][k]+dis[k][j]:dis[i][j]; int flag; for(i=1;i<=n;i++) { flag=0; for(j=1;j<=n;j++) { if(i!=j) if(dis[i][j]!=INF || dis[j][i]!=INF) flag++; } if(flag==n-1)tot++; } printf("%d\n",tot); } return 0; }