【POJ】Cow Contest 闭包传递

题目链接POJ-3660


题目描述

N个选手,如果A比B强,B比C强,则A必比C强
告知若干个强弱关系,问有多少人的排名可以确定
Sample Input
5 5
4 3
4 2
3 2
1 2
2 5
Sample Output
2


思路

floyd算法的基础题;求出所有奶牛的对应关系,如果第i头奶牛可以赢 a 个牛, 且输给 m个牛, 若 n + m == 总奶牛个数-1。则它的排名就是确定的!
mat[i][j] = 1表示 第i头奶牛可以赢第j头奶牛
mat[i][j] = 0表示,第i头奶牛和第j头奶牛的关系不确定;
所以递推关系为 如果 第i头奶牛赢第k头奶牛 , 第k头奶牛赢第j头奶牛, 则必有第i头奶牛赢第j头奶牛;据此,我们利用floyd算法即可ac此题!


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstring>
using namespace std;

#define MAX_N 110
#define MAX_M 5000

int mat[MAX_N][MAX_N], dist_1[MAX_N], dist_2[MAX_N];//dist_1[i] 表示第i头奶牛可以赢得数量 dist_2[i]表示第i头奶牛输的数量

void floyd(int n)
{
for(int k = 1; k<=n; k++)
{
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=n; j++)
{
if(mat[i][k] && mat[k][j])
mat[i][j] = 1;
}
}
}
}

void show(int n)
{
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=n; j++)
{
cout << mat[i][j] << " ";
}
cout << endl;
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(mat, 0, sizeof(mat));
int n, m;
cin >> n >> m;
for(int i = 1; i<=m; i++)
{
int x, y;
cin >> x >> y;
mat[x][y] = 1;
}
floyd(n);
//show(n);
memset(dist_1, 0, sizeof(dist_1));
memset(dist_2, 0, sizeof(dist_2));
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=n; j++)
{
if(mat[i][j])
{
dist_1[i]++;
dist_2[j]++;
}
}
}
int ans = 0;
for(int i = 1; i<=n; i++)
if(dist_1[i] + dist_2[i] == n-1)
ans++;
cout << ans;
return 0;
}
-------------本文结束,感谢您的阅读!-------------