POJ 3660 Cow Contest (Floyd)

题目链接:http://poj.org/problem?id=3660

题意是给你n头牛,给你m条关系,每条关系是a牛比b牛厉害,问可以确定多少头牛的排名。

要是a比b厉害,a到b上就建一条有向边......这样建好之后,如果比a牛厉害的牛都能达到a牛,而a牛能到达比a牛差的牛的话,牛的头数又恰好是n-1头,那么a牛的排名则是确定的。

所以用Flody比较方便,要是i到k能到达,k到j能到达,那么i到j就能到达,i就比j厉害。

 #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = ;
bool cost[MAXN][MAXN]; void init() {
memset(cost , false , sizeof(cost));
} int main()
{
int n , m , u , v;
while(cin >> n >> m) {
init();
while(m--) {
cin >> u >> v;
cost[u][v] = true;
}
for(int k = ; k <= n ; k++) {
for(int j = ; j <= n ; j++) {
for(int i = ; i <= n ; i++) {
if(cost[i][k] && cost[k][j])
cost[i][j] = true;
}
}
}
int cont , res = ;
for(int i = ; i <= n ; i++) {
cont = ;
for(int j = ; j <= n ; j++) {
if(cost[i][j] != cost[j][i])
cont += ;
}
if(cont == n - )
res++;
}
cout << res << endl;
}
}
上一篇:ACM: POJ 3660 Cow Contest - Floyd算法


下一篇:POJ 3660 Cow Contest 传递闭包+Floyd