题解：Cow Contest（P3660）

一、题目分析

本题要求根据奶牛之间的比赛胜负关系，确定有多少头奶牛的排名可以被唯一确定。关键要点：

• 若奶牛A战胜B，说明A的技能评分高于B
• 排名唯一确定的条件：明确知道有多少奶牛比它强（X）和比它弱（Y），且X+Y=N-1
• 需通过胜负关系的传递性，推断所有可能的强弱关系

二、解题思路

1. 传递闭包计算：
   使用Floyd-Warshall算法计算任意两头奶牛之间的胜负关系。若A战胜B，且B战胜C，则A必然战胜C，这是传递性的体现。

2. 胜负统计：

   • 对每头奶牛i，统计比它强的奶牛数（能战胜i的奶牛数，包括直接和间接）
   • 统计比它弱的奶牛数（i能战胜的奶牛数，包括直接和间接）

3. 排名判断：
   若一头奶牛的强、弱奶牛数之和等于N-1，说明其排名唯一确定。

三、代码解析

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m;
int dis[105][105];  // dis[i][j]=1表示i能战胜j
int in[105], out[105];  // in[i]为比i强的奶牛数，out[i]为i能战胜的奶牛数
int cnt;  // 排名唯一确定的奶牛数

int main() {
    while (cin >> n >> m) {
        memset(dis, 0, sizeof(dis));
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        cnt = 0;
        
        // 读取比赛结果，记录直接胜负关系
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            dis[u][v] = 1;  // u战胜v
        }
        
        // Floyd-Warshall算法计算传递闭包
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);
                }
            }
        }
        
        // 统计每头奶牛的胜负数
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dis[i][j]) {
                    out[i]++;  // i能战胜j，j比i弱
                    in[j]++;   // i能战胜j，i比j强
                }
            }
        }
        
        // 判断排名是否唯一
        for (int i = 1; i <= n; i++) {
            if (in[i] + out[i] == n - 1) {
                cnt++;
            }
        }
        
        cout << cnt << endl;
    }
    return 0;
}

四、关键步骤解析

1. 传递闭包计算
   Floyd-Warshall算法的核心在于三重循环：
   [ \text{dis}[i][j] = \text{dis}[i][j] \lor (\text{dis}[i][k] \land \text{dis}[k][j]) ]
   表示若i能战胜k且k能战胜j，则i能战胜j。通过中间节点k传递胜负关系。

2. 胜负数量统计

   • $out[i]$：i能战胜的奶牛数（包括直接和间接）
   • $in[i]$：能战胜i的奶牛数（包括直接和间接）

3. 排名唯一性判断
   对于奶牛i，若已知有$in[i]$头奶牛比它强，$out[i]$头奶牛比它弱，且：
   [ \text{in}[i] + \text{out}[i] = N - 1 ]
   说明i与所有其他奶牛的强弱关系已知，排名唯一确定。

五、示例解析

以样例输入为例：

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

1. 直接胜负关系：

   • 4战胜3、2；3战胜2；1战胜2；2战胜5

2. 传递闭包计算：

   • 4战胜3，3战胜2 → 4战胜2（已存在）
   • 1战胜2，2战胜5 → 1战胜5
   • 4战胜2，2战胜5 → 4战胜5
   • 3战胜2，2战胜5 → 3战胜5
     最终$dis$矩阵包含所有间接胜负关系。

六、注意事项

1. Floyd-Warshall循环顺序：
   必须按照$k→i→j$的顺序循环，确保中间节点k在i和j之前处理，正确传递关系。

2. 矩阵初始化：
   初始时$dis[i][j]=0$，表示未知胜负关系，通过输入和传递性更新为1。

3. 数据范围：
   N≤100时，Floyd-Warshall的时间复杂度O(N³)=10⁶，完全可行。若N更大，可使用DFS/BFS计算传递闭包。

4. 自环处理：
   题目中奶牛技能评分唯一，无需处理i=j的情况，$dis[i][i]$始终为0（无意义）。

七、复杂度分析

• 时间复杂度：O(N³+M)，其中M为比赛轮数。
  Floyd-Warshall占主导，N=100时约10⁶次操作。
• 空间复杂度：O(N²)，存储胜负矩阵和统计数组。

八、扩展思考

1. 传递闭包的其他实现：

   • 对每头奶牛进行BFS/DFS，计算能到达的节点（战胜的奶牛），时间复杂度O(N(M+N))。
   • 对于稀疏图（M远小于N²），BFS/DFS可能更高效。

2. 排名唯一性的本质：
   若奶牛i的强、弱关系构成全序关系（与所有其他奶牛可比），则排名唯一，这等价于$in[i]+out[i]=N-1$。