P4197 Peaks

2018-09-08 16:07:24


题意:给定一个无向图,询问从一个点出发只经过不超过指定边权的边能到达的点的第 $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;
}