526互联

Codeforces Round 888 (Div. 3)G. Vlad and the Mountains（数据结构，图论）

发布时间 2023-08-28 12:26:40作者: XiCen

题目链接：https://codeforces.com/contest/1851/problem/G

 

大致题意：

 

给出n个点m条边的无向图，每个点有点权h【i】。从点 i 到 点 j会消耗 h【j】 - h【i】 的能量，如果小于0，那么就是恢复对应绝对值的能量。

 

进行q次询问，每次询问包含起点s，终点t，能量e，能量在移动过程 中不能小于0，问是否能从s到t；

 

解题思路：

 

转化问题（结合律，然后抵消中间项），相当于不经过h【s】 + e的点，s和e是否连通；

 

然后无向图连通问题可以用并查集来维护；

 

考虑离线做法，我们对能量进行排序（从小到大）；

 

然后依次建边合并，查询即可；

 

时间复杂度：O（nlogn）；

 

代码：

 

#include<bits/stdc++.h>

const int N = 2e5 + 5;
int p[N], h[N];

int FIND(int x) {
    return p[x] = (x == p[x] ? x : FIND(p[x]));
}

struct I {
    int u, v, h, op, id;
};

bool my_cmp(I a, I b) {
    if (a.h != b.h)return a.h < b.h;
    if (a.op != b.op)return a.op < b.op;
    return a.id < b.id;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int T;
    std::cin >> T;
    while (T--) {
        int n, m;
        std::cin >> n >> m;
        for (int i = 1; i <= n; ++i)std::cin >> h[i], p[i] = i;
        std::vector<I> U;
        for (int i = 1; i <= m; ++i) {
            int a, b;
            std::cin >> a >> b;
            U.push_back({a, b, std::max(h[a], h[b]), 0, N + i});
        }
        int q;
        std::cin >> q;
        for (int i = 1; i <= q; ++i) {
            int a, b, x;
            std::cin >> a >> b >> x;
            U.push_back({a, b, h[a] + x, 1, i});
        }

        std::sort(U.begin(), U.end(), my_cmp);

        /*for (int i = 0; i < U.size(); ++i)
            std::cout << U[i].u << " " << U[i].v << " " << U[i].h << " " << U[i].op << " " << U[i].id << "\n";*/

        std::vector<int> ans(q + 1, 0);

        for (int i = 0; i < U.size(); ++i) {
            if (U[i].op)ans[U[i].id] = (FIND(U[i].u) == FIND(U[i].v));
            else p[FIND(U[i].u)] = FIND(U[i].v);
        }

        for (int i = 1; i <= q; ++i)std::cout << (ans[i] ? "YES\n" : "NO\n");
        std::cout << "\n";
    }

    return 0;
}

不是很难的图论+数据结构的题目，但是码量还是有点大的：）