当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 洛谷P4197 Peaks(Kruskal重构树 主席树)

洛谷P4197 Peaks(Kruskal重构树 主席树)

2018年09月18日  | 移动技术网IT编程  | 我要评论

周总理答记者问,9277,天行宝贝官网

题意

题目链接

往后中文题就不翻译了qwq

sol

又是码农题。。出题人这是强行把kruskal重构树和主席树拼一块了啊。。

首先由于给出的限制条件是<=x，因此我们在最小生成树上走一定是最优的。

考虑把kruskal重构树建出来，重构树上每个新的节点代表的是边权，同时用倍增数组维护出跳2^i步后能走到的值最大的节点

这样，该节点的整个子树内的节点都是可以走到的。

用dfs序+主席树维护出每个节点内h的值，直接查第k大即可

需要注意的是，对于不在原树内的节点，h要设的非常小，或者不插入，以免对答案产生影响

同时h需要离散化

写+调用了整两个小时，，自己的码力还是太弱了qwq

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define pair pair<int, int>
#define mp(x, y) make_pair(x, y)
#define fi first 
#define se second
using namespace std;
const int maxn = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, q, h[maxn], date[maxn], tot, num = 0;
struct edge {
    int u, v, w;
    bool operator < (const edge &rhs) const {
        return w < rhs.w;
    }
}e[maxn];
void addedge(int x, int y, int z) {e[++num] = (edge) {x, y, z};}
int fa[maxn], fd[maxn][22], dis[maxn][22];
int find(int x) {
    if(fa[x] == x) return fa[x];
    else return fa[x] = find(fa[x]);
}
int unionn(int x, int y) {fa[x] = y;}
vector<int> v[maxn];
void build() {
    for(int i = 1; i <= (n << 1); i++) fa[i] = i;
    sort(e + 1, e + num + 1);
    for(int i = 1; i <= num; i++) {
        int x = e[i].u, y = e[i].v, w = e[i].w;
        int fx = find(x), fy = find(y);
        if(fx == fy) continue;
        tot++;
        fa[fx] = tot; fa[fy] = tot;
        v[fx].push_back(tot); v[fy].push_back(tot);
        v[tot].push_back(fx); v[tot].push_back(fy);
        dis[fx][0] = w; dis[fy][0] = w;
        fd[fx][0] = tot; fd[fy][0] = tot;
        if(tot == 2 * n - 1) break;
    }
}
int ls[maxn * 30], rs[maxn * 30], tsiz[maxn * 30], root[maxn], cnt, siz[maxn], dfn[maxn], tra[maxn];
void dfs(int x, int fa) {
    dfn[x] = ++cnt; tra[dfn[x]] = x; siz[x] = 1;
    for(int i = 0; i < v[x].size(); i++) {
        int to = v[x][i];
        if(to == fa) continue;
        dfs(to, x);
        siz[x] += siz[to];
    }
}
void update(int k) {
    tsiz[k] = tsiz[ls[k]] + tsiz[rs[k]];
}
void insert(int &k, int p, int val, int l, int r) {
    k = ++cnt;
    ls[k] = ls[p]; rs[k] = rs[p]; tsiz[k] = tsiz[p];
    if(val == -1) return ;
    tsiz[k]++;
    if(l == r) return ;
    int mid = l + r >> 1;
    if(val <= mid) insert(ls[k], ls[p], val, l, mid);
    else insert(rs[k], rs[p], val, mid + 1, r);
    update(k);
}
void maketree() {
    cnt = 0;
    for(int i = 1; i <= tot; i++) 
        insert(root[i], root[i - 1], h[tra[i]], 1, n);
}
void jump() {
    for(int j = 1; j <= 21; j++) {
        for(int i = 1; i <= tot; i++) {
            fd[i][j] = fd[fd[i][j - 1]][j - 1];
            dis[i][j] = max(dis[fd[i][j - 1]][j - 1], dis[i][j - 1]);
        }
    }
}
int get(int x, int val) {
    for(int i = 21; i >= 0; i--) 
        if(dis[x][i] <= val && fd[x][i] != 0) 
            x = fd[x][i];
    return x;
}
int query(int lt, int rt, int k, int l, int r) {
    int used = tsiz[rs[rt]] - tsiz[rs[lt]];
    if(l == r) {
        if(tsiz[rt] - tsiz[lt] < k) return -1;
        else return l;
    } 
    int mid = l + r >> 1;
    if(k <= used) return query(rs[lt], rs[rt], k, mid + 1, r);
    else return query(ls[lt], ls[rt], k - used, l, mid);
}
 main() {
    //freopen("1.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    tot = n = read(); m = read(); q = read();
    memset(h, -1, sizeof(h));
    for(int i = 1; i <= n; i++) h[i] = read(), date[i] = h[i];
    sort(date + 1, date + n + 1);
    int tmp = unique(date + 1, date + n + 1) - date - 1;
    for(int i = 1; i <= n; i++) h[i] = lower_bound(date + 1, date + n + 1, h[i]) - date;
    for(int i = 1; i <= m; i++) {
        int x = read(), y = read(), z = read();
        // v[x].push_back(mp(y, z));
        // v[y].push_back(mp(x, z));
        addedge(x, y, z); addedge(y, x, z);
    }
    build();
    dfs(tot, 0);
    maketree();
    jump();
    while(q--) {
        int v = read(), x = read(), k = read();
        int top = get(v, x);
        int l = dfn[top], r = dfn[top] + siz[top] - 1;
        int ans = query(root[l], root[r], k, 1, n);
        if(ans == -1) printf("%d\n", -1);
        else printf("%d\n", date[ans]);
    }
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网