題目鏈接：

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

題目大意：

　　有n頭牛，每頭牛都有一個(gè)戰(zhàn)斗值，農(nóng)夫約翰想給這些牛排名次，但是只有m場(chǎng)比賽，約翰想知道有多少頭牛的名次是確定的。

解題思路：

　　是一個(gè)求傳遞閉包的題目，傳遞性就是如果i可以到達(dá)k，k可以到達(dá)j，那么i就可以到達(dá)j，求傳遞閉包就是把圖中所有滿足這樣的性質(zhì)的節(jié)點(diǎn)全部求出來(lái)，我們可以知道任意兩點(diǎn)是否向通。可以用floyd實(shí)現(xiàn)傳遞閉包。

經(jīng)過(guò)分析可知，如果牛a與其他的牛都有關(guān)系（無(wú)論什么關(guān)系），那么牛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++)//統(tǒng)計(jì)與牛a有關(guān)的牛有幾個(gè) 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/alihenaixiao/p/4239983.html

總結(jié)

以上是生活随笔為你收集整理的poj 3660 Cow Contest 传递闭包的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。