旅游网站管理系统源码,北京网络营销北京,学院网站建设报告,徐州建设网站引言
其实很早就学了，但是用的不多一直没有补。做题时突然，想起来了补一下。
感觉Kruskal重构树也算一种数据节构吧。为什么要单独拎出来讲呢？因为感觉博客园里这个知识点讲的都不说很清楚，大家好像都对这个知识点…
引言
其实很早就学了，但是用的不多一直没有补。做题时突然，想起来了补一下。
感觉Kruskal重构树也算一种数据节构吧。为什么要单独拎出来讲呢？因为感觉博客园里这个知识点讲的都不说很清楚，大家好像都对这个知识点嗤之以鼻（？原谅我语文不好）。新开一个会好找一点。 最后无耻宣一下：数据节构专题学习笔记。
基本信息
性质：
在这棵树上节点u到节点v的LCA是原图u到v路径上边权最值。且如果原图连通这棵树保证为二叉树，共有 \(2N-1\) 个节点。从小到大构建时，父亲权值不小于儿子；从大到小构建时，父亲权值不大于儿子。
其实此类问题也可以用并查集按秩合并+可持久化来维护，但重构树的优点在于可以套树剖、线段树等静态树结构。
建树过程
类似执行最小生成树算法(Kruskal) ，但不直接连边，而是在新图中创建节点代表这条边。具体过程：遍历每条边(u,v,w) 并维护一个并查集。如果uv不联通：新建节点。在并查集里找到u和v的根节点：ru，rv。新建节点将ru和rv合并，把根节点设为该节点。这棵树就是Kruskal重构树。
例题
待更新，last update on 20260717
先来写一道比较板的题 ：P1967 [NOIP 2013 提高组] 货车运输。
注意到题目中有这句话：现在有 \(q\) 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
满足重构树性质，直接套模板。
#include bits/stdc++.h
#define int long long
using namespace std;
const int N=3e5*2+10;
struct EDGE{int u,v,w;}edge[N];int tot=0;
void addedge(int u,int v,int w){edge[++tot]={u,v,w};}
bool cmp(EDGE x,EDGE y){return x.wy.w;}
int fa[N],w[N],trfa[N],dep[N],lg[N];int stfa[N][20];
int fid(int x) {if(x!=fa[x])fa[x]=fid(fa[x]);return fa[x];}
void init(int n,int m) {for(int i=2;i3e5;i++)lg[i]=lg[i/2]+1;for(int i=1;i=n+m;i++){trfa[i]=i;fa[i]=i;}
}
int LCA(int u,int v) {if(dep[u]dep[v])swap(u,v);while(dep[u]dep[v]){int k=lg[dep[u]-dep[v]];u=stfa[u][k];}if(u==v) return u;for(int k=lg[dep[u]];k=0;k--) if(stfa[u][k]!=stfa[v][k]){u=stfa[u][k];v=stfa[v][k];}return trfa[u];
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m; cinnm; init(n,m) ;for(int i=1,u,v;i=m;i++){cinuvw[i]; addedge(u,v,w[i]);}//-----------建树过程-----------sort(edge+1,edge+1+m,cmp) ;for(int i=1;i=m;i++) {int u=edge[i].u,v=edge[i].v;int fau=fid(u),fav=fid(v);if(fau==fav) continue;n++ ;w[n]=edge[i].w;trfa[fau]=trfa[fav]=fa[fau]=fa[fav]=n;} // 在重构树中加入新节点for(int i=n;i=1;i--) dep[i]=dep[trfa[i]]+1;for(int i=1;i=n;i++) stfa[i][0]=trfa[i];for(int i=1;i=19;i++)for(int u=1;u=n;u++) stfa[u][i]=stfa[stfa[u][i-1]][i-1]; //初始化int Q; cinQ;while(Q--) {int u,v; cinuv;if(fid(u)!=fid(v)) cout"-1\n";else coutw[LCA(u,v)]"\n"; // 朴素LCA}//-----------EOF-----------return 0;
}高清无注释版
#include bits/stdc++.h
#define int long long
using namespace std;
const int N=3e5*2+10;
struct EDGE{int u,v,w;}edge[N];int tot=0;
void addedge(int u,int v,int w){edge[++tot]={u,v,w};}
bool cmp(EDGE x,EDGE y){return x.wy.w;}
int fa[N],w[N],trfa[N],dep[N],lg[N];int stfa[N][20];
int fid(int x) {if(x!=fa[x])fa[x]=fid(fa[x]);return fa[x];}
void init(int n,int m) {for(int i=2;i3e5;i++)lg[i]=lg[i/2]+1;for(int i=1;i=n+m;i++){trfa[i]=i;fa[i]=i;}
}
int LCA(int u,int v) {if(dep[u]dep[v])swap(u,v);while(dep[u]dep[v]){int k=lg[dep[u]-dep[v]];u=stfa[u][k];}if(u==v) return u;for(int k=lg[dep[u]];k=0;k--) if(stfa[u][k]!=stfa[v][k]){u=stfa[u][k];v=stfa[v][k];}return trfa[u];
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m; cinnm; init(n,m) ;for(int i=1,u,v;i=m;i++){cinuvw[i]; addedge(u,v,w[i]);}sort(edge+1,edge+1+m,cmp) ;for(int i=1;i=m;i++) {int u=edge[i].u,v=edge[i].v;int fau=fid(u),fav=fid(v);if(fau==fav) continue;n++ ;w[n]=edge[i].w;trfa[fau]=trfa[fav]=fa[fau]=fa[fav]=n;}for(int i=n;i=1;i--) dep[i]=dep[trfa[i]]+1;for(int i=1;i=n;i++) stfa[i][0]=trfa[i];for(int i=1;i=19;i++)for(int u=1;u=n;u++) stfa[u][i]=stfa[stfa[u][i-1]][i-1];int Q; cinQ;while(Q--) {int u,v; cinuv;if(fid(u)!=fid(v)) cout"-1\n";else coutw[LCA(u,v)]"\n";}return 0;
} 旅游网站管理系统源码北京网络营销北京
旅游网站管理系统源码,北京网络营销北京,学院网站建设报告,徐州建设网站引言
其实很早就学了，但是用的不多一直没有补。做题时突然，想起来了补一下。
感觉Kruskal重构树也算一种数据节构吧。为什么要单独拎出来讲呢？因为感觉博客园里这个知识点讲的都不说很清楚，大家好像都对这个知识点…
引言
其实很早就学了，但是用的不多一直没有补。做题时突然，想起来了补一下。
感觉Kruskal重构树也算一种数据节构吧。为什么要单独拎出来讲呢？因为感觉博客园里这个知识点讲的都不说很清楚，大家好像都对这个知识点嗤之以鼻（？原谅我语文不好）。新开一个会好找一点。 最后无耻宣一下：数据节构专题学习笔记。
基本信息
性质：
在这棵树上节点u到节点v的LCA是原图u到v路径上边权最值。且如果原图连通这棵树保证为二叉树，共有 \(2N-1\) 个节点。从小到大构建时，父亲权值不小于儿子；从大到小构建时，父亲权值不大于儿子。
其实此类问题也可以用并查集按秩合并+可持久化来维护，但重构树的优点在于可以套树剖、线段树等静态树结构。
建树过程
类似执行最小生成树算法(Kruskal) ，但不直接连边，而是在新图中创建节点代表这条边。具体过程：遍历每条边(u,v,w) 并维护一个并查集。如果uv不联通：新建节点。在并查集里找到u和v的根节点：ru，rv。新建节点将ru和rv合并，把根节点设为该节点。这棵树就是Kruskal重构树。
例题
待更新，last update on 20260717
先来写一道比较板的题 ：P1967 [NOIP 2013 提高组] 货车运输。
注意到题目中有这句话：现在有 \(q\) 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
满足重构树性质，直接套模板。
#include bits/stdc++.h
#define int long long
using namespace std;
const int N=3e5*2+10;
struct EDGE{int u,v,w;}edge[N];int tot=0;
void addedge(int u,int v,int w){edge[++tot]={u,v,w};}
bool cmp(EDGE x,EDGE y){return x.wy.w;}
int fa[N],w[N],trfa[N],dep[N],lg[N];int stfa[N][20];
int fid(int x) {if(x!=fa[x])fa[x]=fid(fa[x]);return fa[x];}
void init(int n,int m) {for(int i=2;i3e5;i++)lg[i]=lg[i/2]+1;for(int i=1;i=n+m;i++){trfa[i]=i;fa[i]=i;}
}
int LCA(int u,int v) {if(dep[u]dep[v])swap(u,v);while(dep[u]dep[v]){int k=lg[dep[u]-dep[v]];u=stfa[u][k];}if(u==v) return u;for(int k=lg[dep[u]];k=0;k--) if(stfa[u][k]!=stfa[v][k]){u=stfa[u][k];v=stfa[v][k];}return trfa[u];
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m; cinnm; init(n,m) ;for(int i=1,u,v;i=m;i++){cinuvw[i]; addedge(u,v,w[i]);}//-----------建树过程-----------sort(edge+1,edge+1+m,cmp) ;for(int i=1;i=m;i++) {int u=edge[i].u,v=edge[i].v;int fau=fid(u),fav=fid(v);if(fau==fav) continue;n++ ;w[n]=edge[i].w;trfa[fau]=trfa[fav]=fa[fau]=fa[fav]=n;} // 在重构树中加入新节点for(int i=n;i=1;i--) dep[i]=dep[trfa[i]]+1;for(int i=1;i=n;i++) stfa[i][0]=trfa[i];for(int i=1;i=19;i++)for(int u=1;u=n;u++) stfa[u][i]=stfa[stfa[u][i-1]][i-1]; //初始化int Q; cinQ;while(Q--) {int u,v; cinuv;if(fid(u)!=fid(v)) cout"-1\n";else coutw[LCA(u,v)]"\n"; // 朴素LCA}//-----------EOF-----------return 0;
}高清无注释版
#include bits/stdc++.h
#define int long long
using namespace std;
const int N=3e5*2+10;
struct EDGE{int u,v,w;}edge[N];int tot=0;
void addedge(int u,int v,int w){edge[++tot]={u,v,w};}
bool cmp(EDGE x,EDGE y){return x.wy.w;}
int fa[N],w[N],trfa[N],dep[N],lg[N];int stfa[N][20];
int fid(int x) {if(x!=fa[x])fa[x]=fid(fa[x]);return fa[x];}
void init(int n,int m) {for(int i=2;i3e5;i++)lg[i]=lg[i/2]+1;for(int i=1;i=n+m;i++){trfa[i]=i;fa[i]=i;}
}
int LCA(int u,int v) {if(dep[u]dep[v])swap(u,v);while(dep[u]dep[v]){int k=lg[dep[u]-dep[v]];u=stfa[u][k];}if(u==v) return u;for(int k=lg[dep[u]];k=0;k--) if(stfa[u][k]!=stfa[v][k]){u=stfa[u][k];v=stfa[v][k];}return trfa[u];
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m; cinnm; init(n,m) ;for(int i=1,u,v;i=m;i++){cinuvw[i]; addedge(u,v,w[i]);}sort(edge+1,edge+1+m,cmp) ;for(int i=1;i=m;i++) {int u=edge[i].u,v=edge[i].v;int fau=fid(u),fav=fid(v);if(fau==fav) continue;n++ ;w[n]=edge[i].w;trfa[fau]=trfa[fav]=fa[fau]=fa[fav]=n;}for(int i=n;i=1;i--) dep[i]=dep[trfa[i]]+1;for(int i=1;i=n;i++) stfa[i][0]=trfa[i];for(int i=1;i=19;i++)for(int u=1;u=n;u++) stfa[u][i]=stfa[stfa[u][i-1]][i-1];int Q; cinQ;while(Q--) {int u,v; cinuv;if(fid(u)!=fid(v)) cout"-1\n";else coutw[LCA(u,v)]"\n";}return 0;
}