【2026秋招】每日一更第一更

发布于 2024-10-21  89 次阅读


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;
}

绝对不是恋爱脑!