题解：AT_abc257_d [ABC257D] Jumping Takahashi 2

这道题目的答案可以二分，那为什么呢？

因为我们假设找到一个 \(S\) 满足答案，那么我们让 \(S\) 继续变大，那么 $ p_i \times S \ge \lvert x_i - x_j \rvert + \lvert y_i - y_j \rvert $ 这个公式依旧成立。

但是我们让 \(S\) 继续变小，那么公式就不一定成立了，这个时候我们一定能找到一个分界线，左边都不满足要求，右边都满足要求。

我们假设二分后 \(S = M\)，那么怎么判断 \(M\) 这个点能不能跳呢？

因为我们不知道起点，所以我们要枚举每个点把它作为起点看一看能否跳到其他点。

那么怎么看这个点是否能走到另外一个点呢？

可以用 dfs 或者 bfs 。这里就用 dfs 了。在 dfs 时，我们要记两个参数，第一个 \(i\) 表示我们走到了第 \(i\) 个点，第二个参数就是 \(S\)（可以不记第二个参数，把它当作全局变量也行）。

如果这个起点能走到所有的点，那么这个 \(S\) 就可以，否则我们再看其他点行不行，还不行的话，那二分出来的 \(M\) 就不行，还要想其他的办法（详见代码）

再整理一下思路：

• \(1\)、二分。
• \(2\)、枚举起点，然后用 dfs 或 bfs。

那时间复杂度是什么呢？

二分是 \(\mathcal O(\log S)\) 的时间复杂度。

\(S\) 最小是 \(1\)，最大可以是 \(4\times 10^9\)，为什么呢？

因为假设一个点在左下角，一个点在右上角，那么后面 \(\lvert x_i - x_j \rvert + \lvert y_i - y_j \rvert\) 最大是有 \(4\times 10^9\) ，\(p_i\) 最小是 \(1\)，那么 \(S\) 就得等于 \(4\times 10^9\) 才能让等式成立，注意：这边会爆 int。

枚举所有点是 \(\mathcal O(n)\)，dfs 遍历所有边是 \(\mathcal O(n^2)\)，因为边一共有 \(n^2\) 条。所有时间复杂度都乘起来是 \(\mathcal O(n^3\times \log S)\)。

文字不好理解，来看看代码吧!

AC记录

AC code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,cnt;			//cnt记录从当前这个点出发，能跳到多少个点
ll a[205][2],p[205];
bool b[205];		//记录dfs遍历过了哪些点，true为走过,false为没走过inline void dfs(int i, ll S){b[i] = true;++cnt;for (int j = 1; j <= n; j++)if(!b[j] && p[i]*S >= abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]))dfs(j, S);
}
bool check (ll S){for (int i = 1; i <= n; i++) {memset(b, false, sizeof(b));cnt = 0;dfs(i, S);if(cnt == n)return true;}return false;
}int main(){scanf ("%d",&n);for (int i = 1; i <= n; i++)scanf ("%lld%lld%lld", &a[i][0], &a[i][1], &p[i]);ll L = 0, R = 4e9;while (L + 1 < R) {ll M = (L + R) / 2;if (check(M))R = M;elseL = M;}printf ("%lld\n", R);
}