kruskal重构树

~~由于我的语文太菜了~~阅读本文章之前请小心断句 学习kruskal重构树的前置知识： >kruskal算法 >并查集 >树上倍增/Tarjan求lca kruskal重构树基于kruskal算法，能巧妙地求解询问从A点走到B点的所有路径中，最长的边最小值是多少，或者最短的边的最大值之类的问题。 这个东西的本质其实就是把最小生成树上的边权改成了点权，原图的节点会增加n-1个，也会多出一些神奇性质。 以下是性质: 1.(只考虑新节点)根据以下的构造过程，kruskal重构树是一颗二叉树，并符合二叉堆的性质。 2.原树两点间的的最大边权就是kruskal重构树上两点的lca的权值。 3.重构树中代表原树中的点的节点全是叶子节点，其余节点都代表了一条边的边权。 根据这些美妙性质，kruskal重构树可以解决一些**从A点走到B点的所有路径中，最长的边最小值是多少**之类的~~傻逼~~问题 具体的实现:kruskal重构树就是在原本的kruskal算法中(先假设是求最小生成树)，每次查到两个不在同一集合的点，就**新开一个节点**，然后把两个节点的**祖先节点**分别向新节点连边，不计边权，但是要记录新点的点权，就是连接**两个点的边的边权。** 这样一来，新点的点权的含义就是左右子树中的点想要互通，**必须要走至少一条边权等于这个点权的边。** 也就是说，给定两个点，他们想要联通，所经过的所有路径中最短的边的最大值，就是两个点在kruskal重构树上的lca的点权。 虽说kruskal重构树是基于kruskal算法得到的最小生成树上使用，但也可推广到图中两点路径中最短边的最大值的求解。 不理解的话可以拿稿纸手推，~~肯定是构不出反例的~~ > 若一个点能通过一条路径到达，那么我们走最小生成树上的边也一定能到达该节点。 这句话应该是那类傻逼问题的核心了吧 # NOIP2013货车运输 > A国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。 > 对于100%的数据0<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,0000<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,000。 转化问题：求两点之间所有路径中，最短的边的最大值。 Kruskal重构树模板题。每个询问实际上就是询问在最大生成树中的u,v之间的路径的最小边的权值。 构造重构树，边权按照从大到小的顺序排序，第一次使两个集合联通的边，一定是使这两个集合联通的最长的边，把边权当成重构树上的点权，就能转化成lca求解答案。 ```cpp #include<bits/stdc++.h>//kruskal重构树,求两点之间所有的路径中，最短的边的最大值 using namespace std; int n,m,q; int nxt[200010],to[200010],head[50010],w[50010],tot;//重构树的边，w是新树点权 int cnt; int f[50010];//kruskal算法的并查集 int fa[50010][20],dep[50010];//用于求lca int vis[50010]; struct orz//用于kruskal算法 { int x,y,val; }a[100010]; char buf[1<<15],*fs,*ft; inline char getc(){return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++;} inline int read() { int x=0,f=1; char ch=getc(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48); ch=getc();} return x*f; } void put(int x) { if(x==0){putchar('0');putchar('\n');return;} if(x<0){putchar('-');x=-x;} int num=0;char ch[16]; while(x) ch[++num]=x%10+'0',x/=10; while(num) putchar(ch[num--]); putchar('\n'); } inline int my(orz a,orz b) { return a.val>b.val; } inline int find(int x) { int r=x,mid,j=x; while(r!=f[r]) r=f[r]; while(j!=f[j]) mid=f[j],f[j]=r,j=mid; return r; } inline void add(int xx,int yy) { to[++tot]=yy;nxt[tot]=head[xx];head[xx]=tot; } void dfs(int x)//预处理lca { vis[x]=1; for(int ct=head[x];ct;ct=nxt[ct]) { int y=to[ct]; fa[y][0]=x; for(int i=1;i<=15;++i) fa[y][i]=fa[fa[y][i-1]][i-1]; dep[y]=dep[x]+1; dfs(y); } } inline int lca(int x,int y)//求解lca { if(dep[x]<dep[y]) swap(x,y); for(int i=15;i>-1;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; if(x==y) return x; for(int i=15;i>-1;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } int main() { n=read();m=read(); for(int i=1;i<=m;++i) a[i].x=read(),a[i].y=read(),a[i].val=read(); for(int i=1;i<=n;++i)f[i]=i,f[n+i]=n+i;//并查集初始化 cnt=n;sort(a+1,a+m+1,my);//kruskal算法+重构 for(int i=1;i<=m;++i) { int fx=find(a[i].x),fy=find(a[i].y); if(fx!=fy) f[fx]=f[fy]=++cnt,w[cnt]=a[i].val,add(cnt,fx),add(cnt,fy); } for(int i=cnt;i>n;--i)//预处理lca,注意原图可能不联通，所以我们可能构出了一个森林 if(!vis[i]) dep[i]=1,fa[i][0]=i,dfs(i); q=read();//处理询问 for(int i=1;i<=q;++i) { int xx=read(),yy=read(); if(find(xx)!=find(yy)) put(-1);//两点可能不联通 else put(w[lca(xx,yy)]); } return 0; } ``` # NOI2018归程 > 由于题面太长所以不复制了，请自行查找题面。 这道题其实挺好的，巧妙糅合了许多算法和技巧，但均不超过NOIP难度，是一道良好的NOI送分题。(但是spfa已经死了) 解这道题的前置知识： 1. dijkstra算法 2. kruskal重构树 3. 倍增思想 4. lca(树上倍增版) 掌握了这些算法知识，就可以着手解决这道题了。 首先，我们可以用dijkstra求出1到所有点的距离。 我们注意到有一个海拔的参数，这决定我们从出生点可以跑到哪些地方。 转化:求出从出生点能到哪些点以及这些点到1的最短距离。 这时候我们拿出kruskal重构树这个东西(~~实在不好想~~) 按照海拔从高到低重构，由kruskal重构树的二叉堆性质我们发现限制越低我们就能到达越远的地方。 所以我们考虑在新树的节点上存储两个值:海拔、距离。 海拔是指以这个点为根的子树能够互相到达，并且只经过大于等于这个海拔的路径。这时候每个新树节点表示以它为根的子树中的节点可以互相到达，且经过的最低海拔就是该点权值。 距离是指以这个点为子树的所有节点到1的距离的最小值。 这时候我们发现距离和海拔两个参数都符合二叉堆的性质，也就是有单调性，就可以用倍增的算法了。 我们对一个出生点v，求出深度最小的u，使得v在以u为根节点的子树中，并且u点的海拔>限制海拔。 这个点存储的距离就是答案。 因为既然倍增到了u点,就已经保证了u点的子树之间都可以无代价互相到达，这棵子树的叶子就是开车能到达的节点。这些节点到1的距离的最小值自然就是答案。(~~因为总没有其他方法，使得到1步行的距离比先开车再走最短路的距离短了吧，否则就是在扇dijsktra算法的脸啊~~） 其他的就是细节问题了，注意本题强制在线以及T组数据，顺便计算好要开多大的数组。(~~因为数组开小RE两次~~) ```cpp #include<bits/stdc++.h> using namespace std; int nxt[1200010],to[1200010],head[600010],val[1200010],tot; int w[600010],f[600010],fa[600010][21],dis[1200010],vis[1200010],cnt; struct orz1 { int x,y,l,a; }a[400010]; int t,n,m,q,k,s; int v,p,lastans; char buf[1<<15],*ft,*fs; inline char getc(){return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++;} inline int read() { int num=0;char ch=getc(); while(!isdigit(ch))ch=getc(); while(isdigit(ch))num=(num<<1)+(num<<3)+(ch^48),ch=getc(); return num; } inline void put(int x) { if(x==0) {putchar('0');putchar('\n');return ;} if(x<0) {putchar('-');x=-x;} int num=0;char ch[16]; while(x) ch[++num]=x%10+'0',x/=10; while(num) putchar(ch[num--]); putchar('\n'); return ; } priority_queue<pair<int,int> > qq; inline int my(orz1 a,orz1 b){return a.a>b.a;} inline void add(int xx,int yy,int vv) { to[++tot]=yy,val[tot]=vv,nxt[tot]=head[xx],head[xx]=tot; } inline int find(int x) { int r=x,j=x,mid; while(r!=f[r]) r=f[r]; while(j!=f[j]) mid=f[j],f[j]=r,j=mid; return r; } inline void dijkstra(int st) { memset(dis,127,sizeof(dis)); dis[st]=0; qq.push(make_pair(0,st)); while(!qq.empty()) { int x=qq.top().second; qq.pop();vis[x]=1; for(int ct=head[x];ct;ct=nxt[ct]) { int y=to[ct]; if(dis[y]>dis[x]+val[ct]) { dis[y]=dis[x]+val[ct]; qq.push(make_pair(-dis[y],y)); } } } } inline int minmy(int a,int b){return a>b?b:a;} void dfs(int x) { for(int ct=head[x];ct;ct=nxt[ct]) { int y=to[ct]; fa[y][0]=x;for(int i=1;i<=20;++i)fa[y][i]=fa[fa[y][i-1]][i-1]; if(y>n)dfs(y); dis[x]=minmy(dis[x],dis[y]); } } inline int bei(int x) { int u=x; for(int i=20;i>-1;--i) if(fa[u][i]&&w[fa[u][i]]>p) u=fa[u][i]; return dis[u]; } int main() { t=read(); while(t--) { memset(head,0,sizeof(head)); memset(w,0,sizeof(w)); memset(fa,0,sizeof(fa)); memset(vis,0,sizeof(vis));tot=0;lastans=0; n=read(),m=read(); for(register int i=1;i<=m;++i) { int xx=read(),yy=read(),vv=read(),aa=read(); a[i].x=xx,a[i].y=yy,a[i].l=vv,a[i].a=aa; add(xx,yy,vv),add(yy,xx,vv); } dijkstra(1); sort(a+1,a+1+m,my); for(register int i=1;i<=n;++i) f[i]=i,f[n+i]=n+i; cnt=n; for(register int i=1;i<=m;++i) { int fx=find(a[i].x),fy=find(a[i].y); if(fx!=fy) { f[fx]=f[fy]=++cnt; add(cnt,fx,0);add(cnt,fy,0); w[cnt]=a[i].a; } } dfs(cnt); q=read(),k=read(),s=read(); for(register int i=1;i<=q;++i) { v=(read()+k*lastans-1)%n+1,p=(read()+k*lastans)%(s+1); lastans=bei(v); put(lastans); } } return 0; } ```