poj3660 Cow Contest（Floyd-Warshall方法求有向圖的傳遞閉包），warshall算法

poj3660 Cow Contest（Floyd-Warshall方法求有向圖的傳遞閉包），warshall算法

poj3660

題意： 

有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(v^3)的方法求出圖的傳遞閉包。可以位每條邊賦以權值1,然後運行Floyd-Wareshall。如果從  i  到  j  存在一條路徑，則d(i,j)<N,否則d(i,j)=MAX。

 一種改進的算法是：由於我們需要的只是判斷是否從i到j存在一條通路，所以在Floyd-Wareshall中的動態規劃比較中，我們可以把min和+操作改為邏輯or( ||  )和邏輯（&&）。也就是將  d[i][j] = min(d[i][j],  d[i][k]+dist[k][j]);    改成    if(d[i][j] == 1 || (d[i][k] == 1 && d[k][j] == 1))   d[i][j] = 1;

設  d(i,j) ＝ 1表示從 i 到 j 存在一條通路 p，且 p 的所有中間節點都在0,1,2,...,k中, 否則d(i,j)=0。我們把邊(i,j)加入到E*中當且僅當d(i,j)=1。

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
#include<vector>
using namespace std;

int n, m, ans, v[110][110];

void floyd()//求圖的閉包， 把所有可以確定的關系都求出來
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(v[i][j] == 1 || (v[i][k] == 1 && v[k][j] == 1))
                    v[i][j] = 1;
            }
        }
    }
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(v, 0, sizeof(v));
        for(int i = 1; i <= m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            v[x][y] = 1;
        }
        floyd();

        ans = 0;
        for(int i = 1; i <= n; i++)
        {
            int du = 0;
            for(int j = 1; j <= n; j++)//對於每頭牛， 求是否有唯一排名
            {
                if(i == j) continue;
                if(v[i][j] == 1 || v[j][i] == 1)
                    du++;
            }
            if(du == n-1)
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}