P4197 Peaks

Captain_Paul

2018-09-08 16:07:24

Solution

题意:给定一个无向图,询问从一个点出发只经过不超过指定边权的边能到达的点的第$k$大点权 这道题可以离线也可以在线做 bzoj上有强制在线的加强版 离线做法就是用线段树维护联通块,启发式合并即可。 这里采用在线做法:$Kruskal$重构树 这个算法是NOI2018 D1T1的解法 如果有不会的同学可以自行学习 这道题步骤如下: 先构造$Kruskal$重构树 用倍增找到x在最小生成树上的瓶颈(边权不超过y) 然后查询这个点的子树中的第k小值 然后?就没了orzzzzzz ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; const int N=2e5+5,M=5e5+5; struct E { int from,to,dis; inline friend bool operator < (E a,E b) {return a.dis<b.dis;} }e[M]; struct node { int to,nxt; }edge[N<<2]; int n,m,T,num,head[N],fa[N],noww,val[N],cnt,L[N],R[N],tim,tot; int f[N][20],sum[N*30],ls[N*30],rs[N*30],a[N],w[N],t[N],rt[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num]=(node){to,head[from]}; head[from]=num; } int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} inline void Kruskal() { for (reg int i=1;i<=n;i++) fa[i]=i; for (reg int i=1,tt=0;i<=m;i++) { int x=find(e[i].from),y=find(e[i].to); if (x==y) continue; val[++cnt]=e[i].dis; add_edge(cnt,x); add_edge(cnt,y); fa[x]=fa[y]=fa[cnt]=cnt; if (++tt==n-1) break; } } void dfs(int k,int fh) { L[k]=++tim; a[tim]=k; f[k][0]=fh; for (reg int i=1;i<=19;i++) f[k][i]=f[f[k][i-1]][i-1]; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v!=fh) dfs(v,k); } R[k]=tim; } void insert(int &now,int pre,int l,int r,int x) { now=++tot; sum[now]=sum[pre]+1; ls[now]=ls[pre]; rs[now]=rs[pre]; if (l>=r) return; int mid=(l+r)>>1; if (x<=mid) insert(ls[now],ls[now],l,mid,x); else insert(rs[now],rs[now],mid+1,r,x); } int query(int now,int pre,int l,int r,int x) { if (l>=r) return l; int mid=(l+r)>>1,tmp=sum[ls[now]]-sum[ls[pre]]; if (x<=tmp) return query(ls[now],ls[pre],l,mid,x); return query(rs[now],rs[pre],mid+1,r,x-tmp); } int main() { cnt=n=read(),m=read(),T=read(); for (reg int i=1;i<=n;i++) w[i]=t[i]=read(); for (reg int i=1;i<=m;i++) e[i].from=read(),e[i].to=read(),e[i].dis=read(); sort(t+1,t+n+1); sort(e+1,e+m+1); noww=unique(t+1,t+n+1)-t-1; for (reg int i=1;i<=n;i++) w[i]=lower_bound(t+1,t+noww+1,w[i])-t; Kruskal(); dfs(cnt,cnt); for (reg int i=1;i<=cnt;i++) if (a[i]<=n) insert(rt[i],rt[i-1],1,noww,w[a[i]]); else rt[i]=rt[i-1]; while (T--) { int x=read(),y=read(),k=read(),ans; for (reg int i=19;~i;i--) if (val[f[x][i]]<=y) x=f[x][i]; int res=sum[rt[R[x]]]-sum[rt[L[x]-1]]; if (res<k) ans=-1; else ans=t[query(rt[R[x]],rt[L[x]-1],1,noww,res-k+1)]; printf("%d\n",ans); } return 0; } ```