CF1851G Vlad and the Mountains

这是一道关于无向图中能量传递的问题。给定一个无向图，每个点有一个点权表示其高度，从一个点走到另一个点需要消耗对应高度差的能量，如果能量为负值则表示恢复对应绝对值的能量。现在给出多个询问，每个询问包含起点、终点和初始能量，问能否从起点走到终点并保持能量非负。

通过观察可以发现，走过的点的高度不能高于起点高度与初始能量的和。所以问题转化为能否只经过高度不高于 $h_a+e$ 的点到达 $b$。

解决方法是按照 $h_a+e$ 对询问进行排序，在离线查询的过程中不断添加边，并使用并查集来维护点的连通性。

题目大意

给出 $n$ 个点 $m$ 条边的无向图，每个点有点权 $h_i$。从点 $i$ 走到点 $j$ 会消耗 $h_j-h_i$ 的能量，如果小于 $0$ 就是恢复对应绝对值的能量。给出 $q$ 个询问，每个询问包含起点 $s$，终点 $t$，能量 $e$，能量值在移动的过程中不能低于 $0$，问能否从 $s$ 走到 $t$。

思路

不难发现，走过的点的高度不能高于起点高度与初始能量的和。

问题即转化为能不能只走高度不高于 $h_a+e$ 的点到达 $b$。

按照 $h_a+e$ 对询问排序，离线查询并不断加边，用并查集维护点的连通性即可。

代码

int n, m, t, h[maxN + 5], curr, fa[maxN + 5], res[maxN + 5];
struct edge {
    int a, b, maxh;
} ed[maxN + 5];
struct node {
    int a, b, e, id;
} q[maxN + 5];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void solve() {
    cin >> n >> m;
    rep(i, 1, n) fa[i] = i;
    rep(i, 1, n) cin >> h[i];
    rep(i, 1, m) {
        cin >> ed[i].a >> ed[i].b;
        ed[i].maxh = max(h[ed[i].a], h[ed[i].b]);
    }
    sort(ed + 1, ed + 1 + m, [](edge x, edge y) { return x.maxh < y.maxh; });
    cin >> t;
    rep(i, 1, t) res[i] = 0;
    rep(i, 1, t) {
        cin >> q[i].a >> q[i].b >> q[i].e;
        q[i].id = i;
    }
    sort(q + 1, q + 1 + t,
         [](node x, node y) { return h[x.a] + x.e < h[y.a] + y.e; });
    curr = 1;
    rep(i, 1, t) {
        while (ed[curr].maxh <= h[q[i].a] + q[i].e && curr <= m) {
            fa[find(ed[curr].a)] = find(ed[curr].b);
            curr++;
        }
        res[q[i].id] = find(q[i].a) == find(q[i].b);
    }
    rep(i, 1, t) { cout << (res[i] ? "YES\n" : "NO\n"); }
    cout << endl;
}