最小生成树——Kruskal

标题什么是生成树？

对于一张无向图，由$n$个顶点和$n-1$条边构成地联通子图，叫做这个无向图 生成树

最小生成树就是指边权之和最小地生成树

如何求最小生成树？

Kruskal

介绍:

1. 存图时只存每条边地起点、终点，而不关注节点之间地联通关系，所以不需要链式前向星或邻接矩阵
2. 然后使用边权排序，想像自己获得了$n$个点，现在需要给这$n$个点连边。
3. 循环遍历存边地数组，对于每条边，取出它的两个端点：$x$和$y$,同时使用并查集记录点与点之间是否联通。如果联通，则证明该点之间已经存在最优的边(因为权值更小的边已经排到前面去了，会被优先考虑)。如果不联通，就连上这两条边，使用并查集记录。
4. 最后统计出该最小生成树的所有边的边权之和

代码实现

最小生成树模板题目

#include<bits/stdc++.h>
using namespace std;
int read(){int s=0,fl=1;char w=getchar();while(w>'9'||w<'0'){if(w=='-')fl=-1;w=getchar();}while(w<='9'&&w>='0'){s=s*10+(w^48);w=getchar();}return fl*s;
}
void out(int x){if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else out(x/10),putchar(x%10+'0');
}
struct ed{int v,x,y;
}mp[1000010];
int f[1000010],cnt;
bool cmp(ed x,ed y){return x.v<y.v;
}
int find(int x){if(f[x]!=x) f[x]=find(f[x]);return f[x];
}
int n,m,ans;
int main(){n=read();m=read();for(int i=1;i<=m;i++){mp[i].x=read();mp[i].y=read();mp[i].v=read();//存边}sort(mp+1,mp+1+m,cmp);for(int i=1;i<=n;i++){f[i]=i;//初始化并查集}for(int i=1;i<=m;i++){int x=find(mp[i].x);int y=find(mp[i].y);if(x==y) continue;//如果最上层的祖先是一样的，则证明已经联通，跳过该条边f[x]=y;//将两条边的祖先连在一起cnt++;ans+=mp[i].v;//统计和}cnt==n-1?printf("%d",ans):printf("orz");//判断连上的节点数是否是整张图的节点数，如果不是就证明原图不连通，输出orzreturn 0;
}

双倍经验

P1967 [NOIP 2013 提高组] 货车运输

由题意可得$A$国由$n$个点，$m$条边构成，每条边权重为$z$，货车要从节点$x$走到节点$y$，每走一条边，货车的载重量不能超过当前边的权值。
此题在想不到最小生成树的情况下可以使用$Dijkstra$，要求货车最大的载重量，肯定优先选择边权更大的边通过，于是设$d[i]$表示从节点$x$到节点$i$的最大载重。判断逻辑显然可得：

if(new_dis>d[y]){d[y]=new_dis;

堆优化版$Dijkstra$时间复杂度是O_((V+E)logV) 但是这道题$V$=$1e4$,$E$=$5e4$,计算得最终为$8.4e4$,但是这只是单词$Dijkstra$，算上询问次数，总时间约是$2.4e9$,一定超时
如果用离线处理，效率会高一些，但是还是无法通过此题

正解

使用最小生成树和 最近公共祖先(lca) 解决
因为无论如何货车走的路都一定是最大边权的边，然而生成树的性质有一条就是能联通所有节点，所以我们可以先对这张图求 最大生成树

然后对于每个询问$x$和$y$，求出其最近公共祖先$l$,然后在求$lca$途中维护$w[i][j]$表示从节点$i$向上移动 2^j 层后的最大值。

因为求$lca$的过程是倍增进行的，所以总时间复杂度是$O(mlogm+nlogn+qlogn)$

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int read(){int s=0,fl=1;char w=getchar();while(w>'9'||w<'0'){if(w=='-')fl=-1;w=getchar();}while(w<='9'&&w>='0'){s=s*10+(w^48);w=getchar();}return fl*s;
}
void out(int x){if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else out(x/10),putchar(x%10+'0');
}
int n,m,q;
int d[N],f[N],dep[N],fa[N][21];
int head[N],ne[N],to[N],v[N],tot,vis[N],w[N][21];
struct node{int x,y,v;
}mp[N];
bool cmp(node x,node y){return x.v>y.v;//求最大生成树
}
int find(int x){if(f[x]!=x) f[x]=find(f[x]);return f[x];
}
void add(int x,int y,int w){to[++tot]=y;ne[tot]=head[x];head[x]=tot;v[tot]=w;
}
void dfs(int x){vis[x]=1;for(int i=head[x];i;i=ne[i]){int u=to[i];if(vis[u]){continue;}dep[u]=dep[x]+1;fa[u][0]=x;w[u][0]=v[i];dfs(u);}
}
void kru(){for(int i=1;i<=n;i++){f[i]=i;}sort(mp+1,mp+1+m,cmp);for(int i=1;i<=m;i++){int x=find(mp[i].x);int y=find(mp[i].y);if(x==y){continue;}f[x]=y;add(mp[i].x,mp[i].y,mp[i].v);add(mp[i].y,mp[i].x,mp[i].v);}
}
int lca(int x,int y){if(find(x)!=find(y)){return -1;}int ans=2e9;if(dep[x]<dep[y]){swap(x,y);}for(int k=20;k>=0;k--){if(dep[fa[x][k]]>=dep[y]){ans=min(ans,w[x][k]);x=fa[x][k];}}if(x==y) return ans;for(int k=20;k>=0;k--){if(fa[x][k]!=fa[y][k]){x=fa[x][k];y=fa[y][k];}}ans=min(ans,min(w[x][0],w[y][0]));return ans;
}
int main(){n=read();m=read();for(int i=1;i<=m;i++){int x=read();int y=read();int v=read();mp[i].x=x;mp[i].y=y;mp[i].v=v;}q=read();kru();for(int i=1;i<=n;i++){if(vis[i]==1) continue;dep[i]=1;dfs(i);fa[i][0]=i;w[i][0]=2e9;}for(int i=1;i<=20;i++){for(int j=1;j<=n;j++){fa[j][i]=fa[fa[j][i-1]][i-1];w[j][i]=min(w[j][i-1],w[fa[j][i-1]][i-1]);//预处理倍增表}}for(int i=1;i<=q;i++){int x=read();int y=read();out(lca(x,y));putchar('\n');}return 0;
}