引子

啊啊額，從一張圖里抽出幾條邊，組成一棵樹，無環$n?1$條邊，就是生成樹。那么邊權和最小的生成樹就叫最小生成樹，最大生成樹同理。

kruskal最小生成樹

要求kruskal最小生成樹，我們首先用結構體數組接入數據，然后按照每條邊的邊權進行升序排序，接著用并查集判斷每一條邊，看兩邊的端點是否已經在目前的生成樹里連通，否的話就加入這條邊，如果目前邊數$==n?1$，就$break$，在循環外再進行判斷，看并查集數組里面是否有兩個以上的不同的祖宗，是的話就按題目要求輸出，否則輸出目前$dis$數組的總和。

例子

如上圖，我們可以知道有以下7條邊：

1. A$?$B，w=3
2. A$?$C，w=1
3. A$?$E，w=1
4. B$?$D，w=4
5. C$?$D，w=2
6. C$?$E，w=3
7. D$?$E，w=3

排完序是這樣：

1. A$?$C，w=1
2. A$?$E，w=1
3. C$?$D，w=2
4. A$?$B，w=3
5. C$?$E，w=3
6. D$?$E，w=3
7. B$?$D，w=4

接下來我們來枚舉每一條邊，具體過程如下：

1. A$?$B，此時為空圖，直接放進去。

2. A$?$E，加入后并不形成環，可以放進去。

3. C$?$D，放入。

4. A$?$B，也可以放入。

此時，我們已經添加了$n?1$條邊，已經$break$了，所以答案算出最終為7。

實現 $//$這一段每一行都有注釋

//就不給include了
struct edge{//結構體int u,v,w;//來點，去點，邊權
}a[200005];//結構體數組
bool cmp(edge x,edge y){//結構體排序return x.w<y.w;//按照邊權排序
}//一個用于排序的函數
int fa[5005],cnt,ans; //并查集數組，已選邊數，邊權總和
int find(int x){ //并查集必備return fa[x]==x?x:fa[x]=find(fa[x]);//順帶更新fa數組
}//一個用于并查集的函數
int kruskal(){//開始最小生成樹int n,m;//點的數目，邊的數目cin>>n>>m;//輸入數據for(int i=1;i<=m;i++){//輸入每條邊cin>>a[i].u>>a[i].v>>a[i].w;//接入結構體數組}//第一個循環出現了sort(a+1,a+1+m,cmp);//排序for(int i=1;i<=n;i++)fa[i]=i;//并查集數組的初始值for(int i=1;i<=m;i++){//循環每條邊int u=a[i].u,v=a[i].v,w=a[i].w;//拿出a[i]int u=find(u),v=find(v);//跑一邊并查集if(u!=v){//如果祖先不相同fa[v]=u,cnt++,ans+=w;//v認u做祖宗，邊數加一，總和加該邊的邊權}//這是一個ifif(cnt==n-1){//如果邊數達到了n-1break;//退出循環}//這也是一個if}//還有一個循環int sum=0;//查看有幾個祖宗for(int i=1;i<=n;i++){//查看并查集數組if(i==fa[i])sum++;//如果這貨認自己為祖宗，說明他就是一個祖宗}//還有最后的判斷if(sum>=2){//如果有兩個及以上個祖宗，就沒戲了return -1;//看題目要輸出什么就輸出什么}//快結束了return ans;//返回最終結果
}//不要抄襲哦！

kruskal還沒有結束，他還有時間復雜度，O($mlogm$)。$//$華麗結束

prim最小生成樹

額額啊，你沒猜錯，還有prim！讓我們開始吧！
首先，他非常 常見 好寫 簡單 易懂；然后實現有點像dij，畢竟都是圖論；最后，他是一種基于貪心的算法。為什么這么說呢？因為他每次都是找出一個離生成樹距離最小的一個點，然后把該點放入生成樹。

過程&例子

俗話說的好，一張圖頂一堆話……

dis數組={0，\infty， \infty，\infty，\infty$}

還是這圖，但我們這次用prim來寫。

最開始，我們把1號點放進生成樹，此時生成樹和dis長這樣：

dis數組={$0，\infty ，\infty ，\infty ，\infty$} $//$第0輪

然后循環n-1次，每次找出dis數組里值最小且沒被選過的一個點，把它拿出來看看他有哪些邊，如果連向的點也沒被選過，就更新他的dis。生成樹和dis依次如下：

dis數組={$0，3，1，\infty ，1$} $//$第1輪

dis數組={$0，3，1，2，1$} $//$第2輪

dis數組={$0，3，1，2，1$} $//$第3輪

dis數組={$0，3，1，2，1$} $//$第4輪

最終答案為7。

實現

const int d=1e9;//樸素
struct edge{int u,v,w;
};
vector<edge> E[5005];
int dis[5005],n,m;
bool f[5005];
int prim(){for(int i=1;i<=n;i++)dis[i]=d;dis[1]=0;//千萬別忘了for(int i=1;i<n;i++){int mn=d,u=0;for(int k=1;k<=n;k++){if(dis[k]<mn&&!f[k]){mn=dis[k],u=k;}} f[u]=1;//把自己加入生成樹中for(int j=0;j<E[u].size();j++){int v=E[u][j].v,w=E[u][j].w;if(!f[v]){dis[v]=min(dis[v],w);}}}int sum=0;for(int i=1;i<=n;i++){if(dis[i]==d){return -1;}sum+=dis[i];}return sum;
}

const int dd=1e9;//堆優化
struct node{int v,w;bool operator<(const node&a)const{return w>a.w;}
};
int n,m,dis[5005];
bool vis[5005];
vector<node> E[5005];
priority_queue<node> q;
void prim(){int cnt=0;q.push({1,0});while(!q.empty()&&cnt<=n){node d=q.top();q.pop();if(vis[d.v])continue;vis[d.v]=1,dis[d.v]=min(dis[d.v],d.w),cnt++;for(int i=0;i<E[d.v].size();i++){if(!vis[E[d.v][i].v]){q.push({E[d.v][i].v,E[d.v][i].w});}}}
}//知道為什么跟dij很像了吧！

等，時 間 復 雜 度！

樸素 O(n${}^2+m$)
堆優化 O($(n+m)logm$)

kruskal重構樹

啊額啊，生成樹之后還有重構樹，要炸掉了 ! 可惡的kruskal !

重構樹，說白了就是把一張圖改成一棵樹，然后再這棵樹上LCA。

過程&例子

嗯？不懂？好吧，我們還是一樣來張圖：

首先跟前面kruskal最小生成樹的步驟一樣，把所有的邊按照邊權排序。

1. 1 $?$ 2，w=1
2. 2 $?$ 4，w=1
3. 3 $?$ 5，w=2
4. 1 $?$ 4，w=3
5. 5 $?$ 4，w=4
6. 1 $?$ 3，w=5

接著，我們循環把所有的邊拿出來，查看他們的祖宗是否相同，否的話就把這條邊掛在用于LCA的樹上。

咋掛？這時，我們需要擴域，也就是建造虛擬節點，cnt。

循環前把cnt設為n，每次要掛邊時，cnt++，然后讓cnt當u和v的父親，同時更新并查集數組和記錄每個cnt的左兒子節點和右兒子節點的距離的b數組。

以下為得出的樹和各個數組：

	1	2	3	4	5	6	7	8	9
fa	6	6	8	7	8	7	9	9	9
b	/	/	/	/	/	1	1	2	4

現在樹建好了，就等著LCA啦！

實現

#include<bits/stdc++.h>
using namespace std;
struct edge{int u,v,w;
}a[600005];
bool cmp(edge x,edge y){return x.w<y.w;
}
int fa[200005],b[200005],dep[200005],fc[25][200005],cnt;//并查集數組，每個cnt的左兒子節點和右兒子節點的距離，深度，次方父親數組
vector<int> E[200005];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);
}
void dfs(int x,int f){dep[x]=dep[f]+1;for(int i=1;i<=20;i++)fc[i][x]=fc[i-1][fc[i-1][x]];for(int i=0;i<E[x].size();i++){int v=E[x][i];if(v==f)continue;fc[0][v]=x;dfs(v,x);}
}
int LCA(int x,int y){if(dep[x]>dep[y]){swap(x,y);}for(int i=19;i>=0;i--){if(dep[fc[i][y]]>=dep[x]){y=fc[i][y];}}if(x==y)return x;for(int i=19;i>=0;i--){if(fc[i][x]!=fc[i][y]){x=fc[i][x];y=fc[i][y];}}return fc[0][x];
}
int main(){int n,m;cin>>n>>m;cnt=n;for(int i=1;i<=m;i++){cin>>a[i].u>>a[i].v>>a[i].w;}sort(a+1,a+1+m,cmp);for(int i=1;i<=n*2;i++)fa[i]=i;//由于進行了擴域，所以*2for(int i=1;i<=m;i++){//把所有邊拿出來瞅瞅int u=a[i].u,v=a[i].v,w=a[i].w;u=find(u),v=find(v);if(u!=v){fa[v]=fa[u]=++cnt;b[cnt]=w;E[u].push_back(cnt);E[v].push_back(cnt);E[cnt].push_back(u);E[cnt].push_back(v);}}for(int i=1;i<=cnt;i++){//一系列LCAif(i==fa[i]){dfs(i,0);}}int q;cin>>q;while(q--){//q次詢問int x,y;cin>>x>>y;if(find(x)!=find(y)){cout<<"impossible"<<endl;}else{cout<<b[LCA(x,y)]<<endl;}}return 0;
}

俗話說得好，所有的代碼都可以縮成兩行。

#include<bits/stdc++.h> //獻上最后的代碼
using namespace std;struct edge{int u,v,w;}a[600005];vector<int> E[200005];int fa[200005],b[200005],dep[200005],fc[25][200005],cnt,n,m,q;bool cmp(edge x,edge y){return x.w<y.w;}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}void dfs(int x,int f){for(int i=1;i<=20;i++){fc[i][x]=fc[i-1][fc[i-1][x]],dep[x]=dep[f]+1;}for(int i=0;i<E[x].size();i++){int v=E[x][i];if(v==f){continue;}else{fc[0][v]=x,dfs(v,x);}}}int LCA(int x,int y){if(dep[x]>dep[y])swap(x,y);for(int i=20;i>=0;i--){if(dep[fc[i][y]]>=dep[x])y=fc[i][y];}if(x==y)return x;for(int i=20;i>=0;i--){if(fc[i][x]!=fc[i][y])x=fc[i][x],y=fc[i][y];}return fc[0][x];}int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>a[i].u>>a[i].v>>a[i].w;}sort(a+1,a+1+m,cmp);for(int i=1;i<=n*2;i++)fa[i]=i,cnt=n;for(int i=1;i<=m;i++){int u=a[i].u,v=a[i].v,w=a[i].w,fu=find(u),fv=find(v);if(fu!=fv)fa[fu]=fa[fv]=++cnt,b[cnt]=w,E[cnt].push_back(fu),E[cnt].push_back(fv),E[fu].push_back(cnt),E[fv].push_back(cnt);}for(int i=1;i<=cnt;i++)if(fa[i]==i)dfs(i,0);cin>>q;while(q--){int x,y;cin>>x>>y;find(x)!=find(y)?cout<<"impossible\n":cout<<b[LCA(x,y)]<<endl;}return 0;}

完結萬歲！！！