kruskal重构树
https://www.cnblogs.com/zwfymqz/p/9683523.html
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int maxn=200004,maxm=400004; int n,m,lastans,cnt=0,cnt1=0,head[maxn],fa[maxn],dep[maxn<<1],f[maxn<<1][20],vis[maxn],dis[maxn],head1[maxn<<1]; struct node{ int to,next,w; }e[maxm<<1],tr[maxn<<1]; struct heap{ int u,w; }; inline bool operator < (const heap &x,const heap &y){ return x.w>y.w; } struct data{ int u,v,w,hi; }a[maxm]; inline bool operator < (const data &x ,const data &y){ return x.hi>y.hi; } struct node1{ int l,height; }p[maxn<<1]; inline int find(int u){ if(fa[u]==u) return fa[u]; fa[u]=find(fa[u]); return fa[u]; } inline void add(int u,int v,int w){ e[cnt].next=head[u];e[cnt].to=v;e[cnt].w=w;head[u]=cnt++; } inline void add1(int u,int v){ tr[cnt1].next=head1[u];tr[cnt1].to=v;head1[u]=cnt1++; } inline void dij(){ memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); priority_queue<heap>q; dis[1]=0; q.push((heap){1,0}); while(!q.empty()){ heap x=q.top();q.pop(); if(vis[x.u]) continue;vis[x.u]=1; for(int i=head[x.u];i!=-1;i=e[i].next){ int v=e[i].to; if(vis[v]) continue; if(dis[v]>dis[x.u]+e[i].w) { dis[v]=dis[x.u]+e[i].w; q.push((heap){v,dis[v]}); } } } for(int i=1;i<=n;i++) p[i].l=dis[i]; } inline void dfs(int u,int father){ dep[u]=dep[father]+1,f[u][0]=father; for(int i=1;i<=19;i++) f[u][i]=f[f[u][i-1]][i-1]; for(int i=head1[u];i!=-1;i=tr[i].next){ int v=tr[i].to; if(v!=father){ dfs(v,u); p[u].l=min(p[u].l,p[v].l); } } } inline int query(int x,int y){ for(int i=19;i>=0;i--){ if(dep[x]-(1<<i)>0&&p[f[x][i]].height>y) x=f[x][i]; } return p[x].l; } inline void kruskal(){ memset(f,0,sizeof(f)); int sum=n; for(int i=1;i<=(n<<1);i++) fa[i]=i; sort(a+1,a+m+1); for(int i=1;i<=m;i++){ int u=a[i].u,v=a[i].v; int x=find(u),y=find(v); if(x!=y){ add1(++sum,x);add1(sum,y); fa[x]=sum;fa[y]=sum; p[sum].height=a[i].hi; } } dfs(sum,0); int q,k,s;scanf("%d%d%d",&q,&k,&s); while(q--){ int x,y;scanf("%d%d",&x,&y); x=(k*lastans+x-1)%n+1,y=(k*lastans+y)%(s+1); lastans=query(x,y); printf("%d ",lastans); } } int main(){ int T;scanf("%d",&T); while(T--){ lastans=0;cnt=cnt1=0; memset(head,-1,sizeof(head)); memset(head1,-1,sizeof(head1)); memset(e,0,sizeof(e)); memset(tr,0,sizeof(tr)); memset(a,0,sizeof(a)); memset(p,0,sizeof(p)); memset(dep,0,sizeof(dep)); memset(f,0,sizeof(f)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].w,&a[i].hi); add(a[i].u,a[i].v,a[i].w);add(a[i].v,a[i].u,a[i].w); } for(int i=n+1;i<=(n<<1);i++) p[i].l=0x3f3f3f3f; dij(); kruskal(); } return 0; }