Bo来到了一座山脉,山脉中有$n$座山,每座山都有一个高度$h_i$,有些山之间有路径项链,例如$a$到$b$汕头之间有一条路径链接,如果Bo想的话,他可以从$a$山走到$b$山,同样的,也可也从$b$山走到$a$山。
但Bo很懒,如果两座山之间的高度差大于$k$,他就不会走这条路,即$|h_a-h_b|>k$的话,Bo就不会走这条路了。
现在他提出了$q$次的询问,每次询问他都会给出一组$(a,b,k)$,他想知道,如果他从$a$出发,高度差大于$k$的路径他不走,能否找到一条路径使他到达$b$山。
问题转换:无向图中,是否存在一条a->b的路径,路径上的最大权重小于$k$.
分析:由于输入的图确定后查询过程中不会有额外的边再加入,可以将所有求解任务离线处理,即不按照输入顺序解决每个查询,解决所有查询后输出结果
Solution:由于输入的所有边的权重不会改变,在建图的时候可以考虑按照边的权重$w= abs(h[u]-h[v])$,按照权重的升序排序,每次将相同的$w[cnt]$建立在图中,去检查当前状态下是否有所要求的不大于$w[cnt]$的两点的通路,如有,则说明两点之间存在一条路径中最大权重不大于$w[cnt]$的路径。
在此条件下, 我们可以将所有的查询按照权重大小排序,然后随着查询的权重升序关系去判定是否存在当前一种可能的通路。
在判断通路时,只需要考虑当前两点是否在一个图中,因此可以采用并查集来解决这一问题。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int N = 2e5 + 10;
int h[N], f[N];
int n, m, q, u, v, a, b, k;
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void solve() {
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
cin >> h[i]; // 读入高度
f[i] = i; // 初始化并查集
}
map<int, vector<array<int, 2>>> mp; // 用mp[i]存储权重相同为i的边
for (int i = 0; i < m; i++) {
cin >> u >> v;
mp[abs(h[v] - h[u])].push_back({u, v}); // 存入权重
}
// 读入查询,第i个查询记录为qu[i]={a,b,k,i};
vector<array<int, 4>> qu;
for (int i = 0; i < q; i++) {
cin >> a >> b >> k;
qu.push_back({a, b, k, i});
}
// 将查询按照k的降序查询,然后从尾部读出直到为空
sort(qu.begin(), qu.end(), [&](auto &x, auto &y) { return x[2] > y[2]; });
vector<bool> ans(q); // ans记录每个查询的结果
for (auto &x : mp) {
int cnt = x.first; // 处理权重为cnt的边
vector<array<int, 2>> edges = x.second; // 权重为cnt的边的集合
// 当查询不为空,并且按照升序,当前要检查的边权重小于cnt,则检查此结果
while (qu.size() > 0 && qu.back()[2] < cnt) {
ans[qu.back()[3]] = find(qu.back()[0]) == find(qu.back()[1]);
qu.pop_back(); // 结果确定,移除查询
}
for (auto &e : edges) {
f[find(e[0])] = find(e[1]); // 将权重为cnt 的边加入图中
}
}
// 最后如果有查询权重大于最大的边权,需要进行检查
while (qu.size() != 0) {
ans[qu.back()[3]] = find(qu.back()[0]) == find(qu.back()[1]);
qu.pop_back(); // 结果确定,移除查询
}
// 所有结果确定,按顺序输出查询结果
for (int i = 0; i < ans.size(); i++) {
if (ans[i]) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
Comments | NOTHING