題目鏈接：點擊查看

題目大意：給定n頭牛和m個關系，每個關系表示為兩個整數a與b，其意義為a牛能打敗b牛，問可以確定排名的牛的數量。

題目分析：

在這里先說一下關系閉包： ?

關系閉包有三種： 自反閉包（r）， 對稱閉包（s）， 傳遞閉包（t）。

先畫出?R?的關系圖，再畫出?r（R），s（R），?t（R）?的關系圖。

這個題用到的是關系閉包。

復制一段別人的理解：

關系之間具有傳遞性（例如a> b, b> c, 那么a> c）， 在那些已給出的關系基礎上， 通過傳遞性， 把所有可能的關系都找出來。

這里需要先求一下所有牛之間的傳遞閉包， 那么我們這題與傳遞閉包又有什么關系呢。 下面將慢慢解答。?

如果一頭牛被x頭牛打敗，并且可以打敗y頭牛，如果x+y=n-1，則我們容易知道這頭牛的排名就被確定了，所以我們只要將任一

頭牛，可以打敗其他的牛的個數x， 和能打敗該牛的牛的個數y求出來，在遍歷所有牛判斷一下是否滿足x+y=n-1，就知道這個牛

的排名是否能確定了（而傳遞閉包，正好將所有能得出關系都求出來了）， 再將滿足這個條件的牛數目加起來就是所求解。 x可

以看成是入度， y是出度。

在floyd-warshall求每對頂點間的最短路徑算法中，可以通過O()的方法求出圖的傳遞閉包。可以位每條邊賦以權值1，然后運行

Floyd-Wareshall。如果從 ?i ?到 ?j ?存在一條路徑，則d(i,j)<N,否則d(i,j)=MAX。

在這里有兩個細節可以優化一下Floyd：

使用位運算代替加號

適當進行剪枝

直接上代碼了，更詳細的請看注釋：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;int n,m;int maze[N][N];void floyd()//求圖的閉包，可以把所有的關系求出來 {for(int k=1;k<=n;k++)for(int i=1;i<=n;i++){if(!maze[i][k])//剪枝，如果maze[i][j]為0，則maze[i][k]&maze[k][j]必為0， //對于原結果來說沒有影響，故沒有繼續下一層循環的必要continue;for(int j=1;j<=n;j++){maze[i][j]|=maze[i][k]&maze[k][j];}} }int main() { // freopen("input.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){memset(maze,0,sizeof(maze));//因為是求閉包關系，所以全部初始化為0 for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);maze[a][b]=1;//有關系的設置為1，利用位運算能加快速度 }floyd();int ans=0;for(int i=1;i<=n;i++)//外層遍歷一邊n個點{int cnt=0;for(int j=1;j<=n;j++)//內層遍歷一邊除了i點外的n-1個點{if(i==j)continue;if(maze[i][j]||maze[j][i])//maze[i][j]==1表示i能打敗j，maze[j][i]==1表示j能打敗icnt++;}if(cnt==n-1)//如果i點與其余n-1個點都有關系，則i點的關系是可以被確定的ans++;}cout<<ans<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 3660 Cow Contest(最短路变形+闭包传递)的全部內容，希望文章能夠幫你解決所遇到的問題。

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