Kruskal重构树+LCA || BZOJ 3732: Network

题面：https://www.lydsy.com/JudgeOnline/problem.php?id=3732

题解：Kruskal重构树板子

代码：

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 using namespace std;

 inline int rd(){

     int x=,f=; char c=getchar();

     while(c<''||c>''){if(c=='-')f=-; c=getchar();}

     while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

     return f*x;

 }

 const int maxn=<<,maxm=,maxk=,maxl=;

 int N,M,K,fa[maxn],n,D[maxn],A,B,F[maxn][maxl+],Dep[maxn];

 struct Edge{ int u,v,dis; }edge[maxm];

 vector<int>to[maxn];

 inline bool cmp(const Edge&a,const Edge&b){

     return a.dis<b.dis;

 }

 inline int getf(int n){

     if(fa[n]==n) return n;

     fa[n]=getf(fa[n]);

     return fa[n];

 }

 inline void Kruskal(){

     for(int i=;i<=(N<<);i++) fa[i]=i;

     sort(edge+,edge+M+,cmp);

     int cnt=;

     for(int i=;i<=M;i++){

         int x=edge[i].u,y=edge[i].v,d=edge[i].dis;

         int f1=getf(x),f2=getf(y);

         if(f1!=f2){

             n++;

             D[n]=d;

             fa[f1]=fa[f2]=n;

             to[n].push_back(f1);

             to[n].push_back(f2);

             cnt++;

             if(cnt==N-) return;

         }

     }

     return;

 }

 void Dfs(int x,int fa){

     F[x][]=fa;

     Dep[x]=Dep[fa]+;

     for(int i=;i<=maxl;i++)

         F[x][i]=F[F[x][i-]][i-];

     for(int i=;i<(int)to[x].size();i++)

         Dfs(to[x][i],x);

     return;

 }

 inline int LCA(int x,int y){

     if(Dep[x]<Dep[y]) swap(x,y);

     for(int i=maxl;i>=;i--){

         if(Dep[F[x][i]]>=Dep[y])

             x=F[x][i];

     }

     if(x==y) return x;

     for(int i=maxl;i>=;i--)

         if(F[x][i]!=F[y][i])

             x=F[x][i],y=F[y][i];

     return F[x][];

 }

 int main(){

     N=rd(); M=rd(); K=rd();

     n=N;

     for(int i=;i<=M;i++){

         edge[i].u=rd();

         edge[i].v=rd();

         edge[i].dis=rd();

     }

     Kruskal();

     Dfs(n,);

     while(K--){

         A=rd(); B=rd();

         printf("%d\n",D[LCA(A,B)]);

     }

     return ;

 }

---

By:AlenaNuna