POJ 3660 Cow Contest 詳解：Floyd-Warshall 傳遞閉包求確定排名牛數

題目大意

N 頭牛（N ≤ 100），M 場比賽結果（M ≤ 4500），每場 A B 表示 A 勝 B。技能值唯一且固定，故勝負關係具有傳遞性：A 勝 B 且 B 勝 C ⇒ A 勝 C。求能確定確切排名的牛數（即與其他所有牛勝負關係均已知）。

核心模型：有向圖傳遞閉包

建立鄰接矩陣 win[i][j] 表示 i 是否勝 j（直接或間接）。傳遞閉包計算後，牛 i 確定排名 ⇔ ∀j≠i, win[i][j] || win[j][i] 成立（即與其餘 N-1 頭牛均有已知勝負關係）。

Floyd-Warshall 算法

三重循環計算傳遞閉包：

for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (win[i][k] && win[k][j])
                win[i][j] = true;

時間複雜度 O(N³) = 10⁶，N=100 完全可接受。

完整代碼

#include 
using namespace std;

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        vector> win(n+1, vector(n+1, false));
        for (int i = 0; i < m; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            win[a][b] = true;  // a 勝 b
        }
        
        // Floyd-Warshall 傳遞閉包
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                if (win[i][k])  // 微優化：i 能到 k 才內層循環
                    for (int j = 1; j <= n; ++j)
                        if (win[k][j]) win[i][j] = true;
        
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int known = 0;
            for (int j = 1; j <= n; ++j)
                if (i != j && (win[i][j] || win[j][i])) ++known;
            if (known == n - 1) ++ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}

範例驗證

輸入：

5 5
4 3
4 2
3 2
1 2
2 5

勝負關係：

• 4 > 3 > 2 > 5
• 4 > 2
• 1 > 2

傳遞閉包後：

• 牛 2：輸給 1,3,4；贏 5 → 已知 4 關係 ✓
• 牛 5：輸給 1,2,3,4 → 已知 4 關係 ✓
• 牛 1：贏 2,5；與 3,4 關係未知 ✗
• 牛 3：贏 2,5；輸給 4；與 1 關係未知 ✗
• 牛 4：贏 2,3,5；與 1 關係未知 ✗

輸出：2（牛 2 和 5）✓

複雜度分析

• 時間：O(N³ + M) = 10⁶ + 4500 ≈ 10⁶
• 空間：O(N²) = 10⁴ bool

優化技巧

1. 位運算加速：用 bitset<101> 存儲每行，內層循環變為 win[i] |= win[k]，利用 CPU 位並行加速 64 倍
2. 提前剪枝：if (win[i][k]) 守衛內層循環
3. 拓撲序優化：若圖為 DAG，可按拓撲序 DP，但本題 Floyd 更簡潔

關鍵點總結

1. 傳遞閉包是「已知勝負關係推導未知關係」的標準模型
2. 確定排名條件：與所有其他節點連通（有向圖中雙向可達其一）
3. N ≤ 100 時 Floyd-Warshall 為首選，代碼簡短、不易出錯
4. 輸入可能多組測試用例，用 while(scanf(...)==2) 讀取

總結

POJ 3660 是 Floyd-Warshall 算法的直接應用題。核心在於建立正確的有向圖模型，理解「確定排名」等價於「與所有其他節點存在已知勝負關係」。對於小規模節點（N ≤ 200）的傳遞閉包問題，Floyd 算法是性價比最高的選擇。