kruskal重构树

不同问题的“最优”有不同含义，有的是“最小”，有的是“最大”。本篇博客“最小”就是“最优”。

用kruskal求最小生成树时，假设现在要把 ( u , v ) 加入生成树；

新建一个节点cnt，使 cnt 权值为 dis [ u ] [ v ] ，并连接 ( cnt , u ) , ( cnt , v )；

最后新建点与原有点形成了一个树形结构，这就是kruskal重构树。

从建树过程我们可以看出，所有原有节点都是叶子节点。

受加入顺序的限制，对于新建点，后加的点一定比先加的点权值大。

从重构树的角度来说，对于新建点，其祖先的权值一定比这个点大。

所以我们说，重构树是满足堆性质的

不难想到，两个节点的LCA就是最小生成树上两点之间的最长边。

那么，kruskal重构树可以解决什么问题呢？

它可以将连通块的问题转化到树上。

举个例子：

给出一张无向连通图，边有边权。询问s,k，表示从s出发，不经过边权超过k的边，最多到达多少个点。

可以将原图重构，在重构树上从s出发，倍增找到权值不超过k的深度最小的祖先fa。

那么以fa为根的子树的叶子节点都可以经过权值不超过k的边互相到达。

重构过程实际上是以边权为特征值，将满足特征值的节点加到一个子树内，将连通块的问题转移到了树上。

这样做有关特征值的查询时，只需找到相应的根节点就可以了。

归程

实际上就是，求从v出发，只经过海拔小于p的边所到的点中，到1的最短距离。

先来一波最短路，然后按海拔重构，这里构造最大生成树，使得根节点得海拔最低。

然后倍增求祖先的位置。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<string>
  4 #include<cstring>
  5 #include<queue>
  6 #include<algorithm>
  7 #define mkpr make_pair
  8 #define LL long long
  9 using namespace std;
 10 const int N=200005,M=400005;
 11 inline LL read(){
 12     LL x=0;char ch=getchar();
 13     while(ch<'0'||ch>'9')ch=getchar();
 14     while(ch>='0'&&ch<='9'){
 15         x=x*10+ch-'0';
 16         ch=getchar();
 17     }
 18     return x;
 19 }
 20 
 21 LL T,n,m,cnt,q,k,s;
 22 
 23 struct _mp{
 24     int x,y,h;
 25     LL l;
 26 }mp[M<<1];//原图 
 27 
 28 struct node{
 29     int y,nxt;LL l;
 30 }e[M<<1];//复制一份跑最短路 
 31 int he[M<<1],tot=0;
 32 inline void ad(int x,int y,LL l){
 33     ++tot;
 34     e[tot].y=y;e[tot].l=l;e[tot].nxt=he[x];he[x]=tot;
 35 }
 36 
 37 inline void init(){
 38     n=read();m=read();cnt=n;
 39     for(int i=1;i<=m;++i){
 40         mp[i].x=read();mp[i].y=read();mp[i].l=(LL)read();mp[i].h=read();
 41         ad(mp[i].x,mp[i].y,mp[i].l);ad(mp[i].y,mp[i].x,mp[i].l);
 42     }
 43 }
 44 
 45 LL d[M<<1];
 46 int v[N];
 47 priority_queue<pair<LL,int> > que;
 48 inline void dij(){
 49     memset(v,0,sizeof(v));
 50     d[1]=0;que.push(mkpr(0,1));
 51     while(!que.empty()){
 52         int x=que.top().second;que.pop();
 53         if(v[x])continue;
 54         v[x]=1;
 55         for(int i=he[x];i;i=e[i].nxt){
 56             int y=e[i].y;
 57             if(d[y]>d[x]+e[i].l)
 58                 d[y]=d[x]+e[i].l,que.push(mkpr(-d[y],y));
 59         }
 60     }
 61 }
 62 
 63 LL mn[M<<1];
 64 int fa[M<<1][25];
 65 inline void dfs(int now){
 66     mn[now]=d[now];
 67     for(int i=he[now];i;i=e[i].nxt){
 68         int y=e[i].y;
 69         fa[y][0]=now;
 70         dfs(y);
 71         mn[now]=min(mn[now],mn[y]);
 72     }
 73 }//统计每个子树内的点到1的最短距离 
 74 
 75 int f[M<<1],val[M];
 76 inline bool cmp(_mp a,_mp b){
 77     return a.h>b.h;
 78 }
 79 inline int fnd(int x){
 80     return f[x]==x?x:(f[x]=fnd(f[x]));
 81 }
 82 inline void kru(){
 83     memset(he,0,sizeof(he));tot=0;
 84     sort(mp+1,mp+m+1,cmp);
 85     for(int i=1;i<=n;++i)f[i]=i;
 86     for(int i=1;i<=m;++i){
 87         int fx=fnd(mp[i].x),fy=fnd(mp[i].y);
 88         if(fx==fy)continue;
 89         ++cnt;
 90         f[fx]=f[fy]=f[cnt]=cnt;
 91         val[cnt]=mp[i].h;//新建节点 
 92         ad(cnt,fx,0);ad(cnt,fy,0);
 93     }
 94     dfs(cnt);
 95 }
 96 
 97 inline void clr(){
 98     memset(mn,0x3f,sizeof(mn));
 99     memset(he,0,sizeof(he));tot=0;
100     memset(f,0,sizeof(f));
101     memset(d,0x3f,sizeof(d));
102 }
103 
104 int main(){
105     T=read();
106     while(T--){
107         clr();
108         init();
109         dij();
110         kru();
111         for(int j=1;(1<<j)<=cnt;++j){
112             for(int i=1;i<=cnt;++i){
113                 fa[i][j]=fa[fa[i][j-1]][j-1];
114             }
115         }
116         q=read();k=read();s=read();
117         LL ans=0;
118         LL h0,s0;
119         while(q--){
120             s0=read();h0=read();
121             h0=(h0+k*ans)%(s+1);
122             s0=(s0+k*ans-1)%n+1;
123             for(int j=22;j>=0;--j){
124                 if(fa[s0][j]&&val[fa[s0][j]]>h0)s0=fa[s0][j];
125             }
126             printf("%lld
",mn[s0]);
127             ans=mn[s0];
128         }
129     }
130     return 0; 
131 }
132 /*这份代码LL int 混用，空间开的很不严谨。 
133   让人看着很不爽。
134   但我不想改了。 
135 */

我还想过树剖来着