[算法模板]Kruskal重构树
2024-10-19 11:42:09
[算法模板]Kruskal重构树
kruskal重构树是一个很常用的图论算法。主要用于解决u->v所有路径上最长边的最小值,就是找到\(u->v\)的一条路径,使路径上的最长边最小。
图片来自Kruskal重构树学习笔记+BZOJ3732 Network
从上图我们可以看出,kruskal重构树有以下特质:
- 每个原图上的节点一一对应重构树上的叶子节点。
- 重构树上每一个其他节点(正方形)代表原图上的一个边,有点权。
- 重构树是一棵二叉树。
- 重构树是一个二叉堆。(所以两个叶子节点的LCA即为路径上的最大边)
那如何建树呢?显然,在kruskal基础上搞一搞就行了:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 25000
struct gg{
int u,v,w;
}side1[maxn*2];
vector<int> side2[maxn*4];
bool cop(gg x,gg y){return x.w<y.w;}
int ncnt,num[maxn*4],n,m,k,head[maxn],cnt,dep[maxn*4],f[maxn*4][21],fa[maxn*4];
int get(int x){
if(fa[x]==x)return x;
fa[x]=get(fa[x]);
return fa[x];
}
void uni(int x,int y,int w){
int gx=get(x),gy=get(y);
if(gx==gy)return;
ncnt++;num[ncnt]=w;
side2[ncnt].push_back(gx);side2[ncnt].push_back(gy);side2[gx].push_back(ncnt);side2[gy].push_back(ncnt);
fa[gx]=fa[gy]=fa[ncnt]=ncnt;
return;
}
void dfs(int u,int g){
dep[u]=dep[g]+1;f[u][0]=g;
for(int i=1;i<=20;i++)f[u][i]=f[f[u][i-1]][i-1];
for(int i=0;i<(int)side2[u].size();i++){
int v=side2[u][i];if(v==g)continue;
dfs(v,u);
}
return;
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=20;i>=0;i--)if(dep[f[u][i]]>=dep[v])u=f[u][i];
if(u==v)return u;
for(int i=20;i>=0;i--)if(f[u][i]!=f[v][i]){u=f[u][i];v=f[v][i];}
return f[u][0];
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
side1[i]=(gg){u,v,w};
}
for(int i=0;i<=n;i++){fa[i]=i;}
ncnt=n;
sort(side1+1,side1+1+m,cop);
for(int i=1;i<=m;i++){
if(get(side1[i].u)==get(side1[i].v))continue;
uni(get(side1[i].u),get(side1[i].v),side1[i].w);
}
dfs(ncnt,0);
for(int i=1;i<=k;i++){
int a,b;scanf("%d%d",&a,&b);
printf("%d\n",num[lca(a,b)]);
}
return 0;
}
最新文章
- Yii2 行为
- scanf函数与输入缓冲区
- SAP Adapter启动报错
- groovy基础
- Margaritas on the River Walk_背包
- python之for学习
- OpenStack 部署总结之:在CentOS 6.5上使用RDO单机安装icehouse(Ml2+GRE)
- CentOS 挂载 cdrom, iso文件作为源
- Selenium Webdriver元素定位的八种常用方法
- Lintcode400 Maximum Gap solution 题解
- CSS 火焰?不在话下
- Echarts 南海诸岛简图显示位置调整
- [ES]elasticsearch章5 ES的分词(二)
- from组件补充
- 接口由40秒到200ms优化记录
- Windows中查看端口占用及关闭对应进程
- STRING DELIMITED BY SIZE
- Netty 能做什么
- vs2010,vs2012如何连接vss2005,vss2008
- Android 为库(library)创建不同编译环境