題目鏈接：點擊查看

題目大意：有?n?座山峰，每座山峰有他的高度 h[ i ] ，有些山峰之間有雙向道路相連，共?m?條路徑，每條路徑有一個困難值，這個值越大表示越難走。

現在有?q?組詢問，每組詢問詢問從點?v?開始只經過困難值小于等于?x?的路徑所能到達的山峰中第?k?高的山峰，如果無解輸出??1。

題目分析：因為有困難值的限制，所以可以對整個圖跑克魯斯卡爾重構樹，如果對點 v 來說，只能走小于等于 x 的路徑，可以樹上倍增找到權值小于等于 x 的，深度最淺的祖先，顯然這個祖先子樹中的所有點都是可以從點 v 到達的，接下來找第 k 小，就是主席樹的工作了，dfs 序上建一下主席樹就好了

注意，題目中需要求的是第 k 大，而不是第 k 小

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int h[N],f[N],val[N],dp[N][25],L[N],R[N],n,nn,m,q,tot,limit;bool vis[N]; /*主席樹*/ struct Node {int l,r;int sum; }tree[N*20];int cnt,root[N];void init() {root[0]=0;tree[0].l=tree[0].r=tree[0].sum=0;cnt=1; }void update(int num,int &k,int l,int r) {tree[cnt++]=tree[k];k=cnt-1;tree[k].sum++;if(l==r)return;int mid=l+r>>1;if(num<=mid)update(num,tree[k].l,l,mid);elseupdate(num,tree[k].r,mid+1,r); }int query(int i,int j,int k,int l,int r)//i：左端點根節點編號，j：右端點根節點編號，k：第k大的數，l,r:區間[l,r] {int d=tree[tree[j].r].sum-tree[tree[i].r].sum;if(l==r)return l;int mid=l+r>>1;if(k<=d)return query(tree[i].r,tree[j].r,k,mid+1,r);elsereturn query(tree[i].l,tree[j].l,k-d,l,mid); } /*主席樹*/ struct Edge {int u,v,w;bool operator<(const Edge& t)const{return w<t.w;} }edge[N];vector<int>node[N];//鄰接表 /*dfs序+樹上倍增*/ void dfs(int u,int fa) {vis[u]=true;dp[u][0]=fa;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];L[u]=++tot;root[tot]=root[tot-1];if(u<=n)update(h[u],root[tot],1,nn);for(auto v:node[u])dfs(v,u);R[u]=tot; } /*dfs序+樹上倍增*/ /*并查集+克魯斯卡爾重構樹*/ int find(int x) {return f[x]==x?x:f[x]=find(f[x]); }void Ex_Kruskal() {int index=n;for(int i=1;i<=n<<1;i++)f[i]=i;sort(edge+1,edge+1+m);for(int i=1;i<=m;i++){int xx=find(edge[i].u),yy=find(edge[i].v);if(xx!=yy){f[xx]=f[yy]=++index;val[index]=edge[i].w;node[index].push_back(xx);node[index].push_back(yy);}} } /*并查集+克魯斯卡爾重構樹*/ /*離散化*/ vector<int>disc;void discreate() {sort(disc.begin(),disc.end());disc.erase(unique(disc.begin(),disc.end()),disc.end());nn=disc.size();for(int i=1;i<=n;i++)h[i]=lower_bound(disc.begin(),disc.end(),h[i])-disc.begin()+1; } /*離散化*/ int get_pos(int u,int up)//樹上倍增找滿足的祖先 {for(int i=20;i>=0;i--)if(dp[u][i]!=0&&val[dp[u][i]]<=up)u=dp[u][i];return u; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();scanf("%d%d%d",&n,&m,&q);limit=log2(n)+1;for(int i=1;i<=n;i++){scanf("%d",h+i);disc.push_back(h[i]);}discreate();for(int i=1;i<=m;i++)scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);Ex_Kruskal();for(int i=1;i<=n;i++)if(!vis[i])dfs(find(i),0);while(q--){int v,x,k;scanf("%d%d%d",&v,&x,&k);v=get_pos(v,x);if(tree[root[R[v]]].sum-tree[root[L[v]-1]].sum<k)puts("-1");elseprintf("%d\n",disc[query(root[L[v]-1],root[R[v]],k,1,nn)-1]);}return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的洛谷 - P4197 Peaks(Kruskal重构树+dfs序+主席树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。