【题解】P11915 [PA 2025] 瞬间传送 / Teleport
Starrykiller
·
·
题解
考虑二分答案 $l$，枚举加入的边 $(u,v)$。
如果不合法，那么必然存在一对 $s,t$，使得 $\operatorname{dist}'(s,t)\ge l+1$。
预处理出原图的 $\operatorname{dist}$，枚举 $s$。如果 $t$ 不合法，那么必须满足：
- $\operatorname{dist}(s,t)\ge l+1$；
- $\operatorname{dist}(s,u)+\operatorname{dist}(v,t)\ge l+1\implies \operatorname{dist}(v,t)\ge l-\operatorname{dist}(s,u)+1$；
- $\operatorname{dist}(s,v)+\operatorname{dist}(u,t)\ge l+1\implies \operatorname{dist}(u,t)\ge l-\operatorname{dist}(s,v)+1$。
我们枚举了 $u,v,s$。我们可以预处理 $f(u,i)=\{v:\operatorname{dist}(u,v)\ge i\}$，这样判定的时候只需要判定三个集合交集是否非空。
使用 $\texttt{bitset}$ 维护集合，时间复杂度即为 $\mathcal{O}(n^3\cdot n/w \cdot \log n)=\mathcal{O}(n^4 \log n / w)$。
有一个显然的剪枝：如果 $(u,v)$ 已经合法，直接返回 `true` 即可。这样在官方数据下跑得飞快。（如果不加这个剪枝，在洛谷上依然可以通过。）
赛时担心被卡加了随机化打乱点权，在洛谷上运行时间为 $\text{311 ms}$。
如果有人能够提供在随机化下能够几乎一定将本做法卡到复杂度上界的数据，欢迎联系我。
```cpp
auto check=[&](int L) {
for (int u=0; u<n; ++u)
for (int v=u+1; v<n; ++v) {
bool flag=true;
for (int s=0; s<n; ++s) {
// dis[s][t]>=L+1
// dis[v][t]>=L+1-dis[s][u]
// dis[u][t]>=L+1-dis[s][v]
int a=max(0,L+1-dis[s][u]), b=max(0,L+1-dis[s][v]);
if ((f[s][L+1]&f[v][a]&f[u][b]).any()) {
flag=false; break;
}
}
if (flag) return true;
}
return false;
};
int l=0, r=(n+1)/2;
while (l<r) {
int mid=(l+r)>>1;
if (check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<'\n';
```