Ranking the Cows Time Limit:?2000MS ? Memory Limit:?65536K Total Submissions:?2248 ? Accepted:?1045 Description Each of Farmer John's?N?cows (1 ≤?N?≤ 1,000) produces milk at a different positive rate, and FJ would like to order his cows according to these rates from the fastest milk producer to the slowest. FJ has already compared the milk output rate for?M?(1 ≤?M?≤ 10,000) pairs of cows. He wants to make a list of?C?additional pairs of cows such that, if he now compares those?C?pairs, he will definitely be able to deduce the correct ordering of all?N?cows. Please help him determine the minimum value of?C?for which such a list is possible. Input Line 1: Two space-separated integers:?N?and?M? Lines 2..M+1: Two space-separated integers, respectively:?X?and?Y. Both?X?and?Y?are in the range 1...N?and describe a comparison where cow?X?was ranked higher than cow?Y. Output Line 1: A single integer that is the minimum value of?C. Sample Input 5 5 2 1 1 5 2 3 1 4 3 4 Sample Output 3 Hint From the information in the 5 test results, Farmer John knows that since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4, cow 2 has the highest rank. However, he needs to know whether cow 1 > cow 3 to determine the cow with the second highest rank. Also, he will need one more question to determine the ordering between cow 4 and cow 5. After that, he will need to know if cow 5 > cow 3 if cow 1 has higher rank than cow 3. He will have to ask three questions in order to be sure he has the rankings: "Is cow 1 > cow 3? Is cow 4 > cow 5? Is cow 5 > cow 3?" Source USACO 2007 March Gold

?

?

題目：FJ想按照奶牛產奶的能力給她們排序。現在已知有N頭奶牛（1 ≤ N ≤ 1,000）。FJ通過比較，已經知道了M（1 ≤ M ≤ 10,000）對相對關系。每一對關系表示為“X Y”，意指X的產奶能力強于Y。現在FJ想要知道，他至少還要調查多少對關系才能完成整個排序。

思路：如果排序可以確定了，潛臺詞就是任意兩頭牛之間的關系都可以確定了。N頭奶牛一共有C(N, 2) = N * (N - 1) / 2對關系。由現在已知的關系如能確認K對關系，則要調查的次數就是C(N, 2) - K。

問題再思考一下就能發現，若u強于v，就連一條由u到v的有向路。兩個節點之間有聯系，就等價于這兩個節點之間有一條有向路。這樣就變成了任兩點之間是否存在路徑問題，用floyd傳遞閉包就可以了。

但最多有1,000頭奶牛，時間復雜度為O(N^3)。肯定會超，思考一下就會發現，枚舉中間節點K之后就開始枚舉起點u和終點v，若u與K，或者 v與K之間根本就不聯通，那么絕對無法松弛。所以說更高效的方式就是起點只檢查能通向K的節點，終點只檢查K能通向的節點，這樣就會把復雜度大大降低，因為邊最多只有10000條。floyd 用邊表實現，學習了。。

?

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 5 using namespace std; 6 7 const int N=1010; 8 9 int map[N][N],pre[N][N],suc[N][N]; //pre記錄前驅，suc記錄后繼 pre[v][0]代表v的前驅的個數,suc[u][0]代表u的后繼的個數 10 11 int main(){ 12 13 //freopen("input.txt","r",stdin); 14 15 int n,m; 16 while(~scanf("%d%d",&n,&m)){ 17 memset(map,0,sizeof(map)); 18 memset(pre,0,sizeof(pre)); 19 memset(suc,0,sizeof(suc)); 20 int u,v; 21 int cnt=m; 22 while(m--){ 23 scanf("%d%d",&u,&v); 24 map[u][v]=1; 25 pre[v][++pre[v][0]]=u; //v的前驅是u 26 suc[u][++suc[u][0]]=v; //u的后繼是v 27 } 28 int i,j,k; 29 for(k=1;k<=n;k++) 30 for(i=1;i<=pre[k][0];i++){ 31 u=pre[k][i]; //k的前驅是u 32 for(j=1;j<=suc[k][0];j++){ 33 v=suc[k][j]; //k的后繼是v 34 if(!map[u][v]){ //u是k的前驅，v是k的后繼 所以u是v的前驅 35 pre[v][++pre[v][0]]=u; //u 和 v 之間也建立關系 36 suc[u][++suc[u][0]]=v; 37 map[u][v]=1; 38 cnt++; 39 } 40 } 41 } 42 printf("%d\n",n*(n-1)/2-cnt); 43 } 44 return 0; 45 }

?

總結

以上是生活随笔為你收集整理的POJ 3275 Ranking the Cows （floyd传递闭包）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。