洛谷P4197 Peaks(Kruskal重构树 主席树)
题意题目链接 往后中文题就不翻译了qwq Sol又是编程之家题。。出题人这是强行把Kruskal重构树和主席树拼一块了啊。。 首先由于给出的限制条件是<=x,因此我们在最小生成树上走一定是最优的。 考虑把Kruskal重构树建出来,重构树上每个新的节点代表的是边权,同时用倍增数组维护出跳2^i步后能走到的值最大的节点 这样,该节点的整个子树内的节点都是可以走到的。 用dfs序+主席树维护出每个节点内H的值,直接查第K大即可 需要注意的是,对于不在原树内的节点,H要设的非常小,或者不插入,以免对答案产生影响 同时H需要离散化 写+调用了整两个小时,,自己的码力还是太弱了qwq #include #include #include #include #define Pair pair #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 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],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 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,r); else return Query(ls[lt],ls[rt],k - used,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,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],N); if(ans == -1) printf("%dn",-1); else printf("%dn",date[ans]); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |