2021 icpc 上海 H. Life is a Game

75 阅读 0 评论 50 点赞

我是靠谱客的博主害羞钥匙，最近开发中收集的这篇文章主要介绍2021 icpc 上海 H. Life is a Game，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

常规做法是kruscal重构树。但是并查集+启发式合并也能很快的AC这题。

给定n个点的点权，m条边的边权，q个询问，每个询问是一开始在点x上，初始能量为k。如果能走到一个点，则k += 点权；如果此时的能量 >= 边权，则能经过这条边。对于每个询问，输出最大能获取的能量。

考虑每加一条边，如果连接了两个连通块 fx 与 fy，则 fx 中某一些能量就能更新，剩下的由于能量不够大所以不能更新。如果对边权从下到大排序的话，那么此时不能更新能量的点，以后肯定再也不能更新了。那么如何得知一个点的能量不能再更新呢？
对于每一个点，建立优先队列：

struct po{
    int val, pos;
    bool operator < (const po &k) const {
        return val > k.val;
    }
};
priority_queue<po> q[N];

q[i]存放的是关于起始点在i的初始能量。如果一个能量能够更新，那么必然有 val + s[fx] >= 边权。反之则不能更新，就写入ans，并且在优先队列中删除。
在q[fx]和q[fy]中删除那些不能更新的后，就该启发式合并了，比较q[fx]和q[fy]的大小，小的往大的身上合并。
一开始我的写法是：访问q[fx]和q[fy]的所有点，能更新的更新后然后放入temp队列中，不能更新的放入ans数组中，直到q[fx]和q[y]都空了，再把temp中的放回q[fy]，就完成了合并的操作。这样子的错误在于，访问了所有的点，q[fy]有可能越来越大，所以复杂度达到了n2。
但是能够更新的是不必马上更新的，也就是不用去访问，所以可以启发式合并，复杂度就变为了nlogn。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5, mod = 1e9 + 7;
struct node{
    int x, y, val;
    bool operator < (const node &k) const {
        return val < k.val;
    }
} a[N];
struct po{
    int val, pos;
    bool operator < (const po &k) const {
        return val > k.val;
    }
};
int fa[N], siz[N];
int s[N], ans[N];
priority_queue<po> q[N];
int getf(int k)
{
    if (k == fa[k]) return k;
    return fa[k] = getf(fa[k]);
}
void add(int x, int val)
{
    while(!q[x].empty()){
        po w = q[x].top();
        if (w.val + s[x] < val) {
            q[x].pop();
            ans[w.pos] = w.val + s[x];
        }
        else break;
    }
}
signed main()
{
    int n, m, ques;
    cin >> n >> m >> ques;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &s[i]);
        fa[i] = i;
        siz[i] = 1;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].val);
    }
    sort(a + 1, a + 1 + m);
    for (int i = 1; i <= ques; i++) {
        int x, k;
        scanf("%lld%lld", &x, &k);
        q[x].push(po{k, i});
    }
    for (int i = 1; i <= m; i++){
        int fx = getf(a[i].x), fy = getf(a[i].y), val = a[i].val;
        if (fx == fy) continue;
        add(fx, val);
        add(fy, val);
        if (q[fx].size() > q[fy].size()) swap(fx, fy);
        fa[fx] = fy;
        s[fy] += s[fx];
        while(!q[fx].empty()) {
            q[fy].push(q[fx].top());
            q[fx].pop();
        }
    }
    int ff = getf(1);
    while(!q[ff].empty()) {
        po w = q[ff].top();
        q[ff].pop();
        ans[w.pos] = w.val + s[ff];
    }
    for (int i = 1; i <= ques; i++) printf("%lldn", ans[i]);
    return 0;
}