两头牛之间的强弱关系不仅可以由输入输出获得,还可以通过A > C, C > B知道A > B,于是就能想到floyd算法了,将AB之间的最短路问题转化成AB之间的胜负问题
如果一头牛和其他n-1头牛之间的胜负问题确定了,那它的排名就确定了2333,就是这么简单。。。
代码
#include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<vector>usingnamespacestd;constintmaxn=105;intg[maxn][maxn];intn,m;voidfloy(){for(intk=1;k<=n;k++){for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(g[i][k]==1&&g[k][j]==1){/* A > C, C > B -> A > B */g[i][j]=1;g[j][i]=-1;}elseif(g[i][k]==-1&&g[k][j]==-1){/* A < C, C < B -> A < B */g[i][j]=-1;g[j][i]=1;}}}}}intmain(){cin>>n>>m;while(m--){inta,b;scanf("%d %d",&a,&b);g[a][b]=1;g[b][a]=-1;}floy();intans=0;for(inti=1;i<=n;i++){intcnt=0;for(intj=1;j<=n;j++)if(g[i][j])cnt++;if(cnt==n-1)ans++;}cout<<ans;return0;}
多源最短路径
思路
代码