POJ 3660 Cow Contest：傳遞閉包判斷可確定排名的牛

題目大意

N (≤ 100) 隻牛，技能值互不相同。M (≤ 4500) 場比賽，結果為 A 勝 B。技能高者必勝。給出比賽結果，問有多少隻牛的**絕對排名**（即與所有其他牛的勝負關係均已知）可以被確定。保證結果無矛盾。

建模與解法

• 建有向圖：邊 A→B 表示 A 勝 B（技能 A > B）。
• 傳遞性：若 A > B 且 B > C，則 A > C。需求**傳遞閉包**。
• 對牛 i，若它能到達的牛數 + 能到達它的牛數 = N-1，則其排名確定（與其他所有牛關係已知）。

算法：Floyd-Warshall 遞推閉包

bool g[105][105]; // g[i][j] = i 勝 j
int deg[105];     // 確定關係計數

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

// 統計每頭牛的確定關係數
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        if (g[i][j]) { deg[i]++; deg[j]++; }

// 答案：deg[i] == n-1 的牛數
int ans = 0;
for (int i = 1; i <= n; ++i) if (deg[i] == n-1) ++ans;

複雜度

• Floyd：O(N³) = 10⁶，N=100 極快。
• 空間：O(N²) = 10⁴。

完整代碼

#include 
#include 
using namespace std;
const int MAXN = 105;
bool g[MAXN][MAXN];
int deg[MAXN];

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        memset(g, 0, sizeof(g));
        memset(deg, 0, sizeof(deg));
        for (int i = 0; i < m; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            g[a][b] = true;
        }
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    if (g[i][k] && g[k][j]) g[i][j] = true;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (g[i][j]) { deg[i]++; deg[j]++; }
        int ans = 0;
        for (int i = 1; i <= n; ++i) if (deg[i] == n-1) ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

總結

POJ 3660 是傳遞閉包的直接應用。N ≤ 100 時 Floyd 最簡潔；若 N 較大可用拓撲排序 + bitset 優化。關鍵洞見：排名確定 ⇔ 與所有其他點在閉包中可達或可達它。