牛客网提高组模拟赛第七场 T3 洞穴

题意：有向图，问是否存在从 $a$ 到 $b$ 长度为 $L$ 的路径。

状压dp+bitset+倍增优化

取中间点 $k$，若存在 $i$ 到 $k$ 长度为 $p$ ，从 $k$ 到 $j$ 长度为 $q$ ，则状态转移得到存在 $i$ 到 $j$ 长度为 $p+q$ 的路径。

所以 $dp[i][j][k]\in \{0,1\}$ 表示从 $i$ 到 $k$ 是否存在长度为 $j$ 的路径。但是显然这是存不下的，所以把 $j$ 变为存在长度为 $2^j$ 的路径倍增。之所以能这样优化与本题边长都为 $1$ 有关。由于每个 $l$ 都能被拆为几个二进制的和，所以最终查询时对 $l$ 再处理。

状态转移方程为

$$dp[i][j+1]|=dp[k][j],(dp[i][j][k]=1)$$

查询时由低到高遍历 $l$，设当前能到点集为 $S$，当前距离为 $L_1$，则距离为 $L_1+(1<<i)$ 能到的点集为 $\bigcup_{u\in S}dp[u][i]$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n, m, Q;
bitset<110>dp[110][40], ans;
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		dp[u][0][v] = 1;
	}
	for (int j = 0; j < 30; j++)
		for (int i = 1; i <= n; i++)
			for (int k = 1; k <= n; k++)
				if (dp[i][j][k])
					dp[i][j + 1] |= dp[k][j];
	cin >> Q;
	while (Q--) {
		int l, u, v;
		ans.reset();
		cin >> l >> u >> v;
		ans[u] = 1;
		for (int i = 0; i < 30; i++) {
			if (l >> i & 1) {
				bitset<110>tmp;
				for (int j = 1; j <= n; j++)
					if (ans[j]) tmp |= dp[j][i];
				ans = tmp;
			}
		}
		puts(ans[v] ? "YES" : "NO");
	}
	return 0;
}