用 Python 整数位集加速 Warshall 传递闭包。
OJ: luogu
题目 ID: B3611
难度:普及
标签:传递闭包Floyd位运算python
创建: 2026-07-17 03:00
更新: 2026-07-17 03:00
后置题目
roj 3182「Sorting It All Out」 排序B 的闭包补全与判环完全照搬 A 教的整数位集 Warshall 位或（bits[lo] |= 1<<hi 后跑同一循环），只是把该步放进逐条加边循环并额外用 bit_count 判全序roj 2045usaco-3.1.6 邮票B 的第三步把邮资可达性编码成整数位集，用 `reachable << s` 表示集合整体加 s、按位或表示求并，直接沿用 A 教的「可达集合编码成整数位集并用大整数 OR 合并」这一步，只是把 Warshall 的行并入换成按面值平移的 K 轮集合迭代，并额外叠加最少张数建模与上界 K·maxA。roj 1383刻录光盘(cdrom)B 的 bitset 正解第三步直接复用 A 教的 Warshall 位集转移：A 的「i 能到 k 就把 k 的整行可达集并入 i」在 B 代码里就是 `reach = [r | rk if r >> k & 1 else r for r in reach]`，B 在此闭包之上再叠加取转置列 pred、判 pred⊆reach 与 SCC 去重计数的求源分量流程。
题意
由有向图邻接矩阵求任意两点是否可达。
思路
每一行可达集合编码成整数位集。若 i 能到 k，就把 k 的整行可达集合并入 i；这正是 Warshall 转移，但一次 OR 同时处理全部终点。
Python 知识
- Python 大整数天然是可变长位集。
mask |= value << index编码一行邻接矩阵。- 右移与按位与逐位恢复输出。
代码
python
import sys
input = sys.stdin.buffer.readline
n = int(input())
rows = []
for _ in range(n):
mask = 0
for index, value in enumerate(map(int, input().split())):
mask |= value << index
rows.append(mask)
for middle in range(n):
middle_bit = 1 << middle
middle_row = rows[middle]
# 非常巧妙的使用 为运算来优化传递闭包,
# 使得算法n^2
for start in range(n):
if rows[start] & middle_bit:
rows[start] |= middle_row
for mask in rows:
print(*(mask >> index & 1 for index in range(n)))也可以直接按朴素的 Warshall 三重循环写，只把最内层循环的布尔运算换成按位或：
python
import sys
type Graph = list[list[int]]
def solve(data):
n = next(data)
G = [ [next(data) for _ in [0] * n] for i in range(n) ]
for middle in range(n):
for i in range(n):
if G[i][middle] == 0 :
continue
for j in range(n):
G[i][j] |= (G[i][middle] & G[middle][j])
return G
if __name__ == "__main__":
data = iter(map(int, sys.stdin.buffer.read().split()))
g = solve(data)
print('\n'.join(' '.join(map(str, row)) for row in g))原有 C++ 版本仍保留：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-17 01:40
* update_at: 2026-07-17 01:40
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}复杂度
进行 O(n^2) 次大整数 OR，空间 O(n^2) 位。
总结
布尔矩阵行可以压成整数，把最内层循环交给底层位运算。