poj 3660 Cow Contest 传递闭包

题目链接：

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

题目大意：

　　有n头牛，每头牛都有一个战斗值，农夫约翰想给这些牛排名次，但是只有m场比赛，约翰想知道有多少头牛的名次是确定的。

解题思路：

　　是一个求传递闭包的题目，传递性就是如果i可以到达k，k可以到达j，那么i就可以到达j，求传递闭包就是把图中所有满足这样的性质的节点全部求出来，我们可以知道任意两点是否向通。可以用floyd实现传递闭包。

经过分析可知，如果牛a与其他的牛都有关系（无论什么关系），那么牛a的名次就是确定的。

1 #include <vector> 2 #include <queue> 3 #include <cstdio> 4 #include <cstring> 5 #include <cstdlib> 6 #include <iostream> 7 #include <algorithm> 8 using namespace std; 9 #define maxn 110 10 11 int map[maxn][maxn]; 12 int n; 13 14 void init (); 15 void floyd (); 16 17 int main () 18 { 19 int m; 20 while (scanf ("%d %d", &n, &m) != EOF) 21 { 22 init (); 23 while (m --) 24 { 25 int a, b; 26 scanf ("%d %d", &a, &b); 27 map[a][b] = 1; 28 } 29 floyd (); 30 for (int i=1; i<=n; i++)//统计与牛a有关的牛有几个 31 for (int j=0; j<=n; j++) 32 if (map[i][j]) 33 map[0][i] ++, map[0][j] ++; 34 35 36 int sum = 0; 37 for (int i=1; i<=n; i++) 38 if (map[0][i] == n - 1) 39 sum ++; 40 printf ("%d\n", sum); 41 } 42 return 0; 43 } 44 45 void init () 46 { 47 int i, j; 48 for (i=0; i<maxn; i++) 49 for (j=0; j<maxn; j++) 50 map[i][j] = 0; 51 } 52 void floyd () 53 { 54 int i, j, k; 55 for (k=1; k<=n; k++) 56 for (i=1; i<=n; i++) 57 for (j=1; j<=n; j++) 58 if (map[i][k] && map[k][j])//传递性 59 map[i][j] = 1; 60 }

 

转载于:https://www.cnblogs.com/alihenaixiao/p/4239983.html

总结

以上是生活随笔为你收集整理的poj 3660 Cow Contest 传递闭包的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。