P2245 星际导航
这是一道模板题，借这道模板解释 Kruskal 重构树的构造与作用。
定义
Kruskal 重构树是基于 Kruskal 的最小生成树算法在无向图中得出的树所构造而成的树。
构造
上图是样例
上图是样例的最小生成树
C++
void ks(){
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+m+1);
cn=n;
for(int i=1;i<=m;i++){
int x=find(e[i].u),y=find(e[i].v);
if(x!=y){
fa[x]=fa[y]=++cn,fa[cn]=cn,w[cn]=e[i].w;
g[cn].push_back(x),g[cn].push_back(y);
}
}
}以上是构造 Kruskal 重构树的代码。不难发现，其核心是在按边排序后用一个新点链接两点，并作为并查集的代表。
以上就是根据样例构造出的 Kruskal 重构树，括号中的表示点权。
性质
- 一颗二叉树
- 是大根堆（最小生成树的基础上）
- 原图中两个点间所有路径上的边最大权值的最小值 = 最小生成树上两点简单路径的边最大权值 = Kruskal 重构树上两点 LCA 的点权。
那么根据这个性质，这道模板题就做出来了。
代码：
C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
struct node{
int u,v,w;
bool operator <(const node &a)const{
return w<a.w;
}
}e[N];
vector<int> g[N];
int n,m,q,cn;
int fa[N],w[N],up[N][20],dep[N];
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void ks(){
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+m+1);
cn=n;
for(int i=1;i<=m;i++){
int x=find(e[i].u),y=find(e[i].v);
if(x!=y){
fa[x]=fa[y]=++cn,fa[cn]=cn,w[cn]=e[i].w;
g[cn].push_back(x),g[cn].push_back(y);
}
}
}
void dfs(int u,int f){
up[u][0]=f,dep[u]=dep[f]+1;
for(int i=1;i<=19;i++) up[u][i]=up[up[u][i-1]][i-1];
for(int v:g[u]){
if(v==f) continue;
dfs(v,u);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--){
if(dep[up[x][i]]>=dep[y]) x=up[x][i];
}
if(x==y) return x;
for(int i=19;i>=0;i--){
if(up[x][i]!=up[y][i]){
x=up[x][i],y=up[y][i];
}
}
return up[x][0];
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
ks();
for(int i=1;i<=cn;i++){
if(i==fa[i]) dfs(i,0);
}
cin>>q;
while(q--){
int x,y;
cin>>x>>y;
if(find(x)!=find(y)) cout<<"impossible\n";
else cout<<w[lca(x,y)]<<"\n";
}
return 0;
}P1967 [NOIP 2013 提高组] 货车运输
这道题和模板基本一样，只不过要求的是两点间所有路径上边的最小值的最大值，和上题相反，要用最大生成树。这里取个巧，把边权变负，直接套模板，输出时再变正即可。
代码：
C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
struct node{
int u,v,w;
bool operator <(const node &a)const{
return w<a.w;
}
}e[N];
vector<int> g[N];
int n,m,q,cn;
int fa[N],w[N],up[N][20],dep[N];
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void ks(){
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+m+1);
cn=n;
for(int i=1;i<=m;i++){
int x=find(e[i].u),y=find(e[i].v);
if(x!=y){
fa[x]=fa[y]=++cn,fa[cn]=cn,w[cn]=e[i].w;
g[cn].push_back(x),g[cn].push_back(y);
}
}
}
void dfs(int u,int f){
up[u][0]=f,dep[u]=dep[f]+1;
for(int i=1;i<=19;i++) up[u][i]=up[up[u][i-1]][i-1];
for(int v:g[u]){
if(v==f) continue;
dfs(v,u);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--){
if(dep[up[x][i]]>=dep[y]) x=up[x][i];
}
if(x==y) return x;
for(int i=19;i>=0;i--){
if(up[x][i]!=up[y][i]){
x=up[x][i],y=up[y][i];
}
}
return up[x][0];
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
e[i].w=-e[i].w;
}
ks();
for(int i=1;i<=cn;i++){
if(i==fa[i]) dfs(i,0);
}
cin>>q;
while(q--){
int x,y;
cin>>x>>y;
if(find(x)!=find(y)) cout<<"-1\n";
else cout<<-w[lca(x,y)]<<"\n";
}
return 0;
}
Comments NOTHING