POJ 3660 Cow Contest【floyd】

题目链接:

http://poj.org/problem?id=3660

题目大意:

给出n头牛,m个关系,关系为a的战力比b高。求最后可以确定排名的牛的数量

思路:

1.如果一头牛跟其他所有牛都确定了一个输赢关系,那么该牛的排名就得到了确定,所以用floyd跑一遍传递闭包。然后求得每个点的出度(赢了), 入度(输了)。若该点的度之和为 n - 1 ,即确定排名。

 #include<stdio.h>
#include<string.h>
#define mem(a, b) memset(a, b, sizeof(a))
const int MAXN = ; int n;
int map[MAXN][MAXN]; //表示i赢j
int in[MAXN], out[MAXN]; void floyd()
{
for(int k = ; k <= n; k ++)
for(int i = ; i <= n; i ++)
for(int j = ; j <= n; j ++)
if(map[i][k] && map[k][j])
map[i][j] = ;
} int main()
{
int m;
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
map[a][b] = ;
}
floyd();
for(int i = ; i <= n; i ++)
for(int j = ; j <= n; j ++)
if(map[i][j])
{
out[i] ++;
in[j] ++;
}
int ans = ;
for(int i = ; i <= n; i ++)
if(out[i] + in[i] == n - )
ans ++;
printf("%d\n", ans);
return ;
}
上一篇:ECharts+BaiduMap+HT for Web网络拓扑图应用


下一篇:在Ubuntu上安装VmTools