本文为 Yurchiu 学习最小生成树的笔记以及模板。
最小生成树（MST）其实是最小权重生成树的简称。 个点的连通块，边有权，保留 条边，图仍连通，且边权和最小所形成的树即为最小生成树。最小生成树的“方案”并不是唯一的。
最小生成树
规定：n 点数，m 边数。
Prim
Prim 算法是一种常见并且好写的最小生成树算法。该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。
实现
具体来说，每次要选择距离当前已加入的点集最小的一个结点，以及用新的边更新其他结点的距离。
[1] [2] [8]
[3] [4] [5] [7]
[6] ^ [9]
已加入的点集 已加入的点集之外
^所指为距离当前已加入的点集最小的一个结点。
其实跟 Dijkstra 算法一样，每次找到距离最小的一个点，可以暴力找也可以用堆维护。
堆优化的方式类似 Dijkstra 的堆优化。
在稠密图尤其是完全图上，一般选择暴力 Prim 算法，时间复杂度 ，复杂度比 Kruskal 优，但 不一定 实际跑得更快。
模板
int g[N][N],v[N],d[N];//边，访问标记，距离当前已加入的点集的距离
void prim()
{
for(int i=1;i<=n;i++) d[i]=g[1][i];v[1]=1;
for(int i=1;i<=n-1;i++)
{
int to=-114514,mn=inf;
for(int j=1;j<=n;j++)
if(!v[j]&&d[j]<mn) to=j,mn=d[j];
if(to<0) return;
ans+=mn,v[to]=1;
for(int j=1;j<=n;j++)
if(!v[j]&&d[j]>g[to][j])
d[j]=g[to][j];
}
return;
}
Kruskal
Kruskal 算法是一种常见并且好写的最小生成树算法。
实现
该算法的基本思想是从小到大加入边，是个贪心算法。
使用并查集维护一个森林，查询两个结点是否在同一棵树中，连接两棵树。
如果使用 的排序算法，并且使用 的并查集，就可以得到时间复杂度为 的 Kruskal 算法。
贪心的正确性（比较感性的证明）：
假设图中边权最小的边没被纳入最小生成树，则在生成完毕后，若加入这条边，必定会成为一个基环树。我们发现，删掉环上的其他一边，这个树仍是连通图中所有点的树，而这样必定比以前的生成树要优。
所以最小生成树一定包含一条图中边权最小的边。若纳入这条边，则可以产生一个新的连通块，则这个连通块可作为一个点再参与最小生成树的生成。
注：同理，如果把边集合按边权从大到小枚举，可以得到一个最大生成树。
模板
struct edge{int u,v,len;}e[M*2];
struct UFDS
{
int dad[M],n;
void init(int p){ n=p; for(int i=1;i<=n;i++) dad[i]=i; }
int find(int x)
{
int root=x;
while(root!=dad[root])
root=dad[root];
return root;
}
void union_(int x,int y)
{
int d1=find(x),d2=find(y);
dad[d1]=d2;
return;
}
bool check(int x,int y)
{
int d1=find(x),d2=find(y);
if(d1==d2)
return 1;
return 0;
}
}ufds;//并查集，无需解释
bool cmp(edge a,edge b){ return a.len<b.len; }
void kruskal()
{
int num=0,ru,rv;
sort(e+1,e+cnt+1,cmp);
for(int i=1;i<=m;i++)
{
ru=ufds.find(e[i].u),rv=ufds.find(e[i].v);
if(ru==rv)
continue;
ans+=e[i].len;
ufds.union_(ru,rv);
if(++num==n-1)
break;
}
}
最小瓶颈生成树
即对于图 G 中的生成树上最大的边权值在所有生成树中最小。无向图中，定义上，最小生成树是它的子集。
使用 Kruskal 算法在 G 上构造一个最小生成树，选取的最大边权为 e，我们发现无法使用边权小于 e 的边构造一棵树，因为我们舍弃的边对于构造树来讲是重复的，冗余的。
所以，最小生成树是最小瓶颈生成树。
最小瓶颈路
最小瓶颈路问题是指在一张无向图中，询问一个点对 ，需要找出从 u 到 v 的一条简单路径，使路径上所有边中边权最大值最小。
无向图最小生成树上 u 到 v 的路径一定是 u 到 v 的最小瓶颈路之一。同理也可得到：最大生成树上的路径是最小边权最大路径之一。
使用 Kruskal 算法构造最小生成树，若边 边权为 e，被丢弃，原因是可以使用小于 e 的边构造出一条从 u 到 v 的路径。若边 被纳入最小生成树，则意味着，不能使用小于 e 的边构造一条从 u 到 v 的路径。e 实际上就是从 u 到 v 路径的瓶颈。
所以，最小生成树上 u 到 v 的路径一定是 u 到 v 的最小瓶颈路之一。
例题
P3366 【模板】最小生成树
link。~~这玩意是模板，怎么能是例题呢？~~所以，直接抛代码：
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int M=200000+10,N=5000+10,inf=2147483647;
struct edge{int u,v,len;}e[M*2];
struct UFDS
{
int dad[M],n;
void init(int p){ n=p; for(int i=1;i<=n;i++) dad[i]=i; }
int find(int x)
{
int root=x;
while(root!=dad[root])
root=dad[root];
return root;
}
void union_(int x,int y)
{
int d1=find(x),d2=find(y);
dad[d1]=d2;
return;
}
bool check(int x,int y)
{
int d1=find(x),d2=find(y);
if(d1==d2)
return 1;
return 0;
}
}ufds;
int cnt=0,n,m,ans=0;
int g[N][N],v[N],d[N];
inline void add(int a,int b,int x)
{
e[++cnt]=(edge){a,b,x};
g[a][b]=min(x,g[a][b]);
}
bool cmp(edge a,edge b){ return a.len<b.len; }
void kruskal()
{
int num=0,ru,rv;
sort(e,e+cnt,cmp);
for(int i=1;i<=m;i++)
{
ru=ufds.find(e[i].u),rv=ufds.find(e[i].v);
if(ru==rv)
continue;
ans+=e[i].len;
ufds.union_(ru,rv);
if(++num==n-1)
break;
}
}
void prim()
{
for(int i=1;i<=n;i++) d[i]=g[1][i];v[1]=1;
for(int i=1;i<=n-1;i++)
{
int to=-114514,mn=inf;
for(int j=1;j<=n;j++)
if(!v[j]&&d[j]<mn) to=j,mn=d[j];
if(to<0) return;
ans+=mn,v[to]=1;
for(int j=1;j<=n;j++)
if(!v[j]&&d[j]>g[to][j])
d[j]=g[to][j];
}
return;
}
void yzmain()
{
int t1,t2,t3;
scanf("%d%d",&n,&m);
ufds.init(n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) g[i][j]=0;
else g[i][j]=inf;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
add(t1,t2,t3);
if(n%2) add(t2,t1,t3);
}
if(n%2) prim();
else kruskal();
printf("%d\n",ans);
return;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}
P1265 公路修建
link。
题意
某国有 个城市，它们互相之间没有公路相通。政府决定修建公路。
修建工程分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。
政府审批的规则如下：
如果两个或以上城市申请修建同一条公路，则让它们共同修建；
如果三个或以上的城市申请修建的公路成环，例如，若 A 申请修建公路 AB，B 申请修建公路 BC，C 申请修建公路 CA，则政府将否决其中最短的一条公路的修建申请；
其他情况的申请一律同意。
一轮修建结束后，可能会有若干城市可以通过公路直接或间接相连。这些可以互相连通的城市即组成“城市联盟”。在下一轮修建中，每个“城市联盟”将被看作一个城市，发挥一个城市的作用。
当所有城市被组合成一个“城市联盟”时，修建工程也就完成了。你的任务是计算出将要修建的公路总长度。
题解
首先可以证明，规则 2 是毫无用处的，因为三个以上城市成环的情况是不可能出现的。满足题意的话，A B C 只能组成正三角形。
接下来可以证明，按“轮”进行处理也是没有必要的。
因此只需直接求出最小生成树即可。
Prim 算法的优势：稠密图，尤其是完全图。因为在 Kruskal 算法中，必须事先求出所有边的长度才能对之排序。但是一个有 5000 节点的完全图，这样做的空间、时间开销是巨大的。Prim 算法只在更新点到树的距离时需要用到边长，因此对于这种给坐标的完全图，可以现用现算。
代码
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const long long N=5000+10,inf=2147483647;
struct Pos{long long x,y;}c[N];
long long v[N],n; double d[N],ans=0;
double g(long long a,long long b){return sqrt((c[a].x-c[b].x)*(c[a].x-c[b].x)+(c[a].y-c[b].y)*(c[a].y-c[b].y));}
void prim()
{
for(long long i=1;i<=n;i++) d[i]=g(1,i);v[1]=1;
for(long long i=1;i<=n-1;i++)
{
long long to=-114514;
double mn=inf;
for(long long j=1;j<=n;j++)
if(!v[j]&&d[j]<mn) to=j,mn=d[j];
if(to<0) return;
ans+=mn,v[to]=1;
for(long long j=1;j<=n;j++)
if(!v[j]&&d[j]>g(to,j))
d[j]=g(to,j);
}
return;
}
void yzmain()
{
scanf("%lld",&n);
for(long long i=1;i<=n;i++)
scanf("%lld%lld",&c[i].x,&c[i].y);
prim();
printf("%.2lf",ans);
return;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}
其他题解见 2。
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/7fcca1bd3023/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
