引子

啊啊额，从一张图里抽出几条边，组成一棵树，无环$n-1$条边，就是生成树。那么边权和最小的生成树就叫最小生成树，最大生成树同理。

kruskal最小生成树

要求kruskal最小生成树，我们首先用结构体数组接入数据，然后按照每条边的边权进行升序排序，接着用并查集判断每一条边，看两边的端点是否已经在目前的生成树里连通，否的话就加入这条边，如果目前边数$==n-1$，就$break$，在循环外再进行判断，看并查集数组里面是否有两个以上的不同的祖宗，是的话就按题目要求输出，否则输出目前$dis$数组的总和。

例子

如上图，我们可以知道有以下7条边：

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

排完序是这样：

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

接下来我们来枚举每一条边，具体过程如下：

1. A$\leftrightarrow$B，此时为空图，直接放进去。

2. A$\leftrightarrow$E，加入后并不形成环，可以放进去。

3. C$\leftrightarrow$D，放入。

4. A$\leftrightarrow$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 $\leftrightarrow$ 2，w=1
2. 2 $\leftrightarrow$ 4，w=1
3. 3 $\leftrightarrow$ 5，w=2
4. 1 $\leftrightarrow$ 4，w=3
5. 5 $\leftrightarrow$ 4，w=4
6. 1 $\leftrightarrow$ 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;}

完结万岁！！！