用位集传递闭包统计每头牛已知强于和弱于的数量。
OJ: luogu
题目 ID: P2419
难度:普及
标签:传递闭包位运算偏序python
日期: 2026-07-17 03:00
题意
由比赛胜负关系判断有多少头牛的完整排名可以确定。
思路
胜者指向败者，位集 Warshall 求所有间接胜负。对牛 i，它能到达的数量加能够到达它的数量若为 n-1，说明与其他每头牛的强弱都已确定，排名唯一。
Python 知识
- 一行可达集合编码成 Python 整数。
mask >> cow & 1检查其他行是否能到达该牛。- 布尔值可直接参与整数求和。
代码
python
import sys
input = sys.stdin.buffer.readline
n, contests = map(int, input().split())
reachable = [0] * n
for _ in range(contests):
winner, loser = map(int, input().split())
reachable[winner - 1] |= 1 << (loser - 1)
for middle in range(n):
bit = 1 << middle
for start in range(n):
if reachable[start] & bit:
reachable[start] |= reachable[middle]
answer = 0
for cow in range(n):
known = reachable[cow].bit_count() + sum(mask >> cow & 1 for mask in reachable)
answer += known == n - 1
print(answer)原有 C++ 版本仍保留：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 5;
int n, m;
bool can_beat[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
can_beat[u][v] = true;
}
// Warshall 传递闭包：
// 如果 i 能赢 k，k 又能赢 j，那么 i 也能赢 j。
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
if (!can_beat[i][k]) {
continue;
}
for (int j = 1; j <= n; j++) {
if (can_beat[k][j]) {
can_beat[i][j] = true;
}
}
}
}
int answer = 0;
for (int i = 1; i <= n; i++) {
int known = 0;
for (int j = 1; j <= n; j++) {
if (i == j) {
continue;
}
if (can_beat[i][j] || can_beat[j][i]) {
known++;
}
}
if (known == n - 1) {
answer++;
}
}
cout << answer << '\n';
return 0;
}复杂度
进行 O(n^2) 次位集 OR，空间 O(n^2) 位。
总结
排名可确定等价于该元素与所有其他元素都存在已知偏序关系。