自学内容网 自学内容网

【题解 && Kruskal重构树 && LCA】 星际导航

星际导航

在这里插入图片描述


分析:

这也是一个比较老的题目了
今天突然想学一下kruskal重构树,就做到了这个题。

首先我们要明白,为什么这道题的路径一定是在最小生成树里?
或许是我们惯有的经验:最小的最大或者最大的最小无非两种套路:
二分答案以及最小生成树。
仔细一想发现二分答案在这道题并不可行。
于是我们将矛头转向了最小生成树。
但是为什么呢?

首先我们明白,两个点之间的路径,其实是一个生成子图,或者说生成子树。
想要最大边最小,其实感性理解一下,就等价于让两个点连通的代价最小。
我们回想最小生成树的思路,这个时候有两个点x和y
如果x和y不连通,说明我们这个时候甚至找不到x和y的一条路径,也就无法求最大边的最小值。
这个时候如果我们在加入一条边v,使得x和y能够连通
那么ok,显然这条边就是我们想找的答案。
也就是x到y路径上的最大边的最小值。
为什么是最大边?
因为这是让x和y连通加入的最后一条边,前面的加边都比他小
为什么是最大的最小?
因为如果我们不要这条边,而选择后面的边,让x和y能够连通,后面的边显然都比他大。
所以又是最小。

这里的最大与最小其实是从两个维度看,理解不同罢了。

那么明白之后其实这道题就变成了Kruskal重构树的模板题。
Kruskal就是将最小生成树的边化为点
边权变成点权
这样子就得到了一颗二叉树
而且原图上的点都是叶子结点
原图上两点的边权就是他们的LCA
因为我们建树加边的时候是按照边权从小到大加边
所以满足越上面的点的边权越大。
于是两个点之间的最大边权就变成了重构树上的LCA的点权。
那么这题就结束了


#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 3e5+100;
int n,m;
struct E{
int x,y,z;
}e[3*N];
int Fa[N][30];
int fa[N];
int cnt;
int v[N*2];
vector < int > a[N];
int d[N]; 
#define pb push_back

bool cmp(E x,E y){
return x.z < y.z;
}

int getfa(int x){
return x == fa[x]?x:fa[x] = getfa(fa[x]);
}

void Dfs(int x,int faa,int de){
d[x] = de;
Fa[x][0] = faa;
for (int i = 0; i < a[x].size(); i++){
int y = a[x][i]; if (y == faa) continue;
Dfs(y,x,de+1);
}
}

void Prefa(){
for (int j = 1; j < 30; j++)
  for (int i = 1; i <= cnt; i++)
    if (Fa[i][j-1] == -1) Fa[i][j] = -1;
    else Fa[i][j] = Fa[Fa[i][j-1]][j-1];
}

int Lca(int x,int y){
if (d[x] < d[y]) swap(x,y);
for (int dd = d[x]-d[y],i=0; dd; dd>>=1,i++)
  if (dd&1) x = Fa[x][i];
if (x == y) return x;
for (int i = 29; i >= 0; i--)
  if (Fa[x][i]!=Fa[y][i]) x = Fa[x][i] , y = Fa[y][i];
return Fa[x][0];
}

signed main(){
scanf("%lld %lld",&n,&m);
for (int i = 1; i <= n; i++) v[i] = 0;
cnt = n;
for (int i = 1,x,y,z; i <= m; i++)
  scanf("%lld %lld %lld",&x,&y,&z),e[i] = {x,y,z};
sort(e+1,e+m+1,cmp);
for (int i = 1; i < N; i++) fa[i] = i;
for (int i = 1; i <= m; i++){
int x = e[i].x , y = e[i].y , z = e[i].z;
x = getfa(x) , y = getfa(y);
if (x == y) continue;
++cnt; v[cnt] = z;
a[cnt].pb(x); a[cnt].pb(y);
a[x].pb(cnt); a[y].pb(cnt);
fa[x] = cnt; fa[y] = cnt;
}
//memset(Fa,-1,sizeof Fa);
for (int i = cnt; i >= 1; i--)
  if (!d[i]) Dfs(i,-1,1);
Prefa();
int q; cin>>q;
while (q--){
int x,y; 
cin>>x>>y;
int X = getfa(x) , Y = getfa(y);
if (X!=Y){
cout<<"impossible"<<endl;
continue;
}
int L = Lca(x,y);
printf("%lld\n",v[L]);
}
return 0;
}

原文地址:https://blog.csdn.net/huang_ke_hai/article/details/140590216

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!