压位BFS
一个 $n$ 个点，$m$ 条边的有向图，当所有边权均为 $1$ 时，求任意两点之间的最短路。
$n\leq 1000,m\leq \frac{n(n-1)}{2}$ 。
多源最短路是一个经典问题，显然可以通过floyd算法在 $O(n^3)$ 的复杂度下求解。同时，考虑到本题中一个特殊的条件：所有边权均为 $1$ ，本题也可以通过01-BFS解决，这显然是 $O(nm)$ 的。
但是以上两种传统做法在稠密图时效率较低，例如本题就无法通过了。对于本题这类01多源最短路问题，我们可以通过bitset进行压位BFS，将复杂度降低至 $O(\frac{n^3}{\omega})$ ，在64位机上就是 $O(\frac{n^3}{64})$ 。这个方法很难通过语言描述解释（懒得写），直接上代码：
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 1001;
bitset<SIZE> g[SIZE], vis, now;
int dis[SIZE][SIZE];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
memset(dis, -1, sizeof(dis));
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int x;
cin >> x;
if (x) {
g[i].set(j);
}
}
}
for (int i = 1; i <= n; i++) {
vis.reset(); // 清空已遍历的数组
vis.set(i);
queue<int> q;
q.push(i);
dis[i][i] = 0;
while (!q.empty()) {
auto top = q.front();
q.pop();
now = g[top] ^ (g[top] & vis); // 去掉已经遍历到的节点
for (int to = now._Find_first(); to != now.size(); to = now._Find_next(to)) { // 本方法的关键: O(n/64) 遍历bitset
dis[i][to] = dis[i][top] + 1;
q.push(to);
}
vis |= now; // 更新已遍历的节点
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << dis[i][j] << " \n"[j == n];
}
}
return 0;
}
配套的题目：01多源最短路，由于是随手自制的，这题数据可能偏弱。
上面这个方法是 $O(\frac{n^3}{64})$ 的关键在于如何 $O(\frac{n}{64})$ 遍历一个bitset数组，也就是这段：
for (int to = now._Find_first(); to != now.size(); to = now._Find_next(to)) { // 本方法的关键: O(n/64) 遍历bitset
...
}
_Find_first()：找从左往右第一个true的位置。_Find_next(p)：找 $p$ 位置以后第一个true的位置，若找不到则返回size()。
这两个方法配合起来遍历bitset所有为 $1$ 的位置就是 $O(\frac{n}{64})$ 的。
看懂了上面的代码，其实就已经学会了压位BFS。
练习题
【模板】01多源最短路
代码已经挂在上面了。
无向图中的最短距离
这题需要多次回答：一个无向图中距离点 $x$ 不超过 $y$ 的点数。因此可以多开一个三维bitset数组dp，设 $dp[i][j]$ 表示到点 $i$ 的距离不超过 $j$ 的点集。在BFS的过程中可以处理出到点 $i$ 的距离正好为 $j$ 的点集，然后就有以下转移式：dp[i][j+1] |= dp[i][j] 。
回答的时候新建一个空的bitset，然后对于所有条件逐个or起来即可：
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 1001;
bitset<SIZE> dp[SIZE][SIZE], g[SIZE], vis, now;
int dis[SIZE][SIZE];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
memset(dis, -1, sizeof(dis));
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].set(v);
g[v].set(u);
}
for (int i = 1; i <= n; i++) {
vis.reset();
vis.set(i);
queue<int> q;
q.push(i);
dis[i][i] = 0;
while (!q.empty()) {
auto top = q.front();
q.pop();
now = g[top] ^ (g[top] & vis);
for (int to = now._Find_first(); to != now.size(); to = now._Find_next(to)) {
dis[i][to] = dis[i][top] + 1;
q.push(to);
}
vis |= now;
}
for (int j = 1; j <= n; j++) {
if (dis[i][j] != -1) {
dp[i][dis[i][j]].set(j);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j + 1] |= dp[i][j];
}
}
while (q--) {
int a;
cin >> a;
vector<pair<int, int>> pr(a);
bitset<SIZE> bs;
for (auto& i : pr) {
cin >> i.first >> i.second;
bs |= dp[i.first][i.second];
}
cout << bs.count() << "\n";
}
return 0;
}
Guard
给一个 $n$ 个点的有向图的邻接矩阵，多次询问
s t k，表示是否存在一条从 $s$ 出发到 $t$ 的路径，长度恰好为 $k$ 。
浙大集训时，Claris出的一道题，虽然思路很容易想到，但是因为当时不知道压位BFS的骚操作，并不会做这题。
假设 $s$ 走到 $t$ 的最短路是 $d$ ，当 $(k-d)\equiv0\pmod{2}$ 并且 $d\leq k$ 是必定有解。这是因为我们可以在一条边上反复横跳，但是万一存在这种情况：假设 $d$ 是奇数，$k$ 是偶数，但是存在从 $s$ 出发到 $t$ 的一条简单路径长度是奇数，这样的话本题就不能简单地通过最短路解决了。
解决上述问题的策略很简单，只需要对每对点求出长度必定为奇数时的最短路和长度必定为偶数时的最短路就好了，通过压位BFS解决，时间复杂度仍然是 $O(\frac{n^3}{64})$ 。需要注意的坑点就是如果某个点是孤立点，那么他到自己的最短路为 $0$ ，但是不可能走出 $>0$ 的路径。
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 2001;
bitset<SIZE> g[SIZE], vis_odd, vis_even, now;
int dis[SIZE][SIZE][2];
bool single[SIZE];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
memset(dis, -1, sizeof(dis));
memset(single, true, sizeof(single));
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
char x;
cin >> x;
if (x == '1') {
g[i].set(j);
single[i] = false;
}
}
}
for (int i = 1; i <= n; i++) {
vis_odd.reset();
vis_even.reset();
vis_even.set(i);
queue<pair<int, int>> q;
q.push({ i,0 });
dis[i][i][0] = 0;
while (!q.empty()) {
auto [u, v] = q.front();
q.pop();
if (v) { // 路径长度为奇数
now = g[u] ^ (g[u] & vis_even);
} else { // 路径长度为偶数
now = g[u] ^ (g[u] & vis_odd);
}
for (int to = now._Find_first(); to != now.size(); to = now._Find_next(to)) {
if (v) {
dis[i][to][0] = dis[i][u][1] + 1;
q.push({ to,0 });
} else {
dis[i][to][1] = dis[i][u][0] + 1;
q.push({ to,1 });
}
}
if (v) {
vis_even |= now;
} else {
vis_odd |= now;
}
}
}
int q;
cin >> q;
while (q--) {
int s, t, k;
cin >> s >> t >> k;
if (s == t && k > 0 && single[s]) {
cout << "No\n";
} else if (dis[s][t][0] >= 0 && dis[s][t][0] <= k && (k - dis[s][t][0]) % 2 == 0) {
cout << "Yes\n";
} else if (dis[s][t][1] >= 0 && dis[s][t][1] <= k && (k - dis[s][t][1]) % 2 == 0) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}