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

题解：Kruskal重构树板子

代码：

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<vector>
 4 using namespace std;
 5 inline int rd(){
 6     int x=0,f=1; char c=getchar();
 7     while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
 8     while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
 9     return f*x;
10 }
11 const int maxn=15005<<1,maxm=30005,maxk=20005,maxl=16;
12 int N,M,K,fa[maxn],n,D[maxn],A,B,F[maxn][maxl+2],Dep[maxn];
13 struct Edge{ int u,v,dis; }edge[maxm];
14 vector<int>to[maxn];
15 inline bool cmp(const Edge&a,const Edge&b){
16     return a.dis<b.dis;
17 }
18 inline int getf(int n){
19     if(fa[n]==n) return n;
20     fa[n]=getf(fa[n]);
21     return fa[n];
22 }
23 inline void Kruskal(){
24     for(int i=1;i<=(N<<1);i++) fa[i]=i;
25     sort(edge+1,edge+M+1,cmp);
26     int cnt=0;
27     for(int i=1;i<=M;i++){
28         int x=edge[i].u,y=edge[i].v,d=edge[i].dis;
29         int f1=getf(x),f2=getf(y);
30         if(f1!=f2){
31             n++;
32             D[n]=d;
33             fa[f1]=fa[f2]=n;
34             to[n].push_back(f1);
35             to[n].push_back(f2);
36             cnt++;
37             if(cnt==N-1) return;
38         }
39     }
40     return;
41 }
42 void Dfs(int x,int fa){
43     F[x][0]=fa;
44     Dep[x]=Dep[fa]+1;
45     for(int i=1;i<=maxl;i++)
46         F[x][i]=F[F[x][i-1]][i-1];
47     for(int i=0;i<(int)to[x].size();i++)
48         Dfs(to[x][i],x);
49     return;
50 }
51 inline int LCA(int x,int y){
52     if(Dep[x]<Dep[y]) swap(x,y);
53     for(int i=maxl;i>=0;i--){
54         if(Dep[F[x][i]]>=Dep[y])
55             x=F[x][i];
56     }
57     if(x==y) return x;
58     for(int i=maxl;i>=0;i--)
59         if(F[x][i]!=F[y][i])
60             x=F[x][i],y=F[y][i];
61     return F[x][0];
62 }
63 int main(){
64     N=rd(); M=rd(); K=rd();
65     n=N;
66     for(int i=1;i<=M;i++){
67         edge[i].u=rd();
68         edge[i].v=rd();
69         edge[i].dis=rd();
70     }
71     Kruskal();
72     Dfs(n,0);
73     while(K--){
74         A=rd(); B=rd();
75         printf("%d\n",D[LCA(A,B)]);
76     }
77     return 0;
78 }

View Code

 

---

By:AlenaNuna