![(中等) POJ 3660 Cow Contest,Floyd。 (中等) POJ 3660 Cow Contest,Floyd。](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
Description
N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.
The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.
Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.
题目就是求有几头牛的排名确定了,用Floyd算法,如果a胜了b,就建边a->b,然后Floyd,然后枚举每一个点,对于这个点,如果所有其余的点与他的位置都确定了的话(也就是两点之间的最短路不为INF),那么这个点就是位置确定的点。
代码如下:
#include<iostream>
#include<cstring>
#include<cstdio> using namespace std; const int INF=10e8; int N,M;
int map1[][]; int main()
{
int a,b;
int ans;
bool ok; while(cin>>N>>M)
{
for(int i=;i<=N;++i)
for(int j=;j<=N;++j)
map1[i][j]= i==j ? : INF; for(int i=;i<=M;++i)
{
cin>>a>>b;
map1[a][b]=;
} for(int k=;k<=N;++k)
for(int i=;i<=N;++i)
for(int j=;j<=N;++j)
map1[i][j]=min(map1[i][j],map1[i][k]+map1[k][j]); ans=N; for(int i=;i<=N;++i)
{
ok=; for(int j=;j<=N;++j)
if(map1[i][j]==INF && map1[j][i]==INF)
{
ok=;
break;
} if(!ok)
--ans;
} cout<<ans<<endl;
} return ;
}