发现我还naive的不会Kruskal重构树
所谓Kruskal重构树 就是在做Kruskal的时候 构造一颗树 对两个即将合并的联通块 新建一个节点 作为这两个联通块的父亲 且这个节点的权值就是那条相连两个联通块的权值
而且这棵树很明显是一个堆
那么对于最初的最小生成树 两个节点路径上的最大/小值 就是重构树上他们的lca
然后就可以解决这道题了
#include<bits/stdc++.h> #define N 15005 #define M 30005 using namespace std; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int n,m,k; struct Data { int from,to,val; }e[M]; int father[2*N],val[2*N]; inline bool cmp(const Data &a,const Data &b) { return a.val<b.val; } inline int getfather(int x) { if(father[x]==x) return x; father[x]=getfather(father[x]); return father[x]; } struct Edge { int to,next,val; }edge[4*N]; int first[2*N],tot; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } void Kruskal() { int sign=n; for(int i=1;i<=2*n;i++) father[i]=i; sort(e+1,e+m+1,cmp); for(int i=1;i<=m;i++) { int fx=getfather(e[i].from),fy=getfather(e[i].to); if(fx!=fy) { father[fx]=father[fy]=++sign; val[sign]=e[i].val; addedge(sign,fx); addedge(fx,sign); addedge(sign,fy); addedge(fy,sign); if(sign==2*n-1) break; } } } int depth[2*N],up[2*N][23]; void dfs(int now,int fa) { depth[now]=depth[fa]+1; up[now][0]=fa; for(int i=1;i<=20;i++) up[now][i]=up[up[now][i-1]][i-1]; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; dfs(vis,now); } } inline int lca(int x,int y) { if(depth[x]<depth[y]) swap(x,y); for(int i=20;i>=0;i--) if(depth[up[x][i]]>=depth[y]) x=up[x][i]; if(x==y) return x; for(int i=20;i>=0;i--) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i]; return up[x][0]; } int main() { read(n); read(m); read(k); for(int i=1;i<=m;i++) read(e[i].from),read(e[i].to),read(e[i].val); Kruskal(); dfs(2*n-1,0);//注意是从2*n-1开始dfs for(int i=1,x,y;i<=k;i++) { read(x); read(y); cout<<val[lca(x,y)]<<'\n'; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9857795.html
