最小生成树
树：无向图中不能形成环，且连接所有顶点($n$个顶点，$n-1$条边)
最小：权值和最小的树
视频动画展示：最小生成树
模板来源（y总）： 最小生成树算法模板
$Kruskal$算法
核心：从小到大挑不多余的边。
步骤： 将所有的边取出 (按照边对应权值从小到大排序)
判断是否存在环，没有就加入，有就跳过判断下一条边
最后直到选择了 n-1 条边
struct Edge
{
int a, b, v;
bool operator< (const Edge &W) const
{
return v < W.v;
}
};
// 并查集——寻找当前集合的代表元素
int find(int x)
{
if (father[x] != x) father[x] = find(father[x]);
return father[x];
}
// 所有边存储在 Edge edges[M];
// 函数返回最小生成树中所有边的总长度
int Kruskal()
{
int res = 0;
// 初始化并查集代表元素
for (int i = 1; i <= n; i ++ ) father[i] = i;
sort(edge, edge + m);
for (int i = 0; i < m; i ++ )
{
int a = edge[i].a, b = edge[i].b;
if (find(a) != find(b))//不能形成一个环就继续
{
res += edge[i].v;
father[find(a)] = find(b);
}
}
return res;
}
$Prim$算法:
核心思想：从顶点出发每次挑一条与当前集合相连的最短边
步骤： 从一个顶点出发，更新所有与该顶点相连的信息(三个数组)
下一次的顶点为 dist 数组里权值最小开始
// st[i] 表示点i是否在当前生成树集合中（是否被选择开始全为false）
// dist[i] 表示点i到当前集合的最短边的长度 （设开始的两条边的权值为INF无穷大）
// g[i][j] 表示点i和点j之间边的长度 （两个点构成一条边）
// 返回值：最小生成树中所有边的总长度
int Prim()
{
int res = 0;
for (int i = 1; i <= n; i ++ )
{
dist[i] = INF;
st[i] = false;
}
dist[1] = 0;
for (int i = 1; i <= n; i ++ )
{
int id = -1, min_dist = INF;
// 寻找最短边
for (int j = 1; j <= n; j ++ )
if (!st[j] && dist[j] < min_dist)
{
id = j;
min_dist = dist[j];
}
st[id] = true;
res += dist[id];
// 用新加入的点更新其余点到生成树的最短边
for (int j = 1; j <= n; j ++ )
if (!st[j])
dist[j] = min(dist[j], g[id][j]);
}
return res;
}
天空之城
注意map映射的用法：把字符串映射为整型
难点：想着如何取标记字符串名字的地方
然后套用 $Kruskal$算法 模板
#include <bits/stdc++.h>
using namespace std;
const int N=2000010;
typedef long long ll;
int pre[N];
struct node{
int a,b,c;
bool operator< (const node & t) const{
return c<t.c;
}
}q[N];
map<string,int > mp;
int find(int x){
if(x!=pre[x]) pre[x]=find(pre[x]);
return pre[x];
}
int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF){
int tot=0;
for(int i=1;i<=n;i++) pre[i]=i;//！！
mp.clear();//多组数据输入 记得清空map
string s;cin>>s;
for(int i=0;i<m;i++){
string a,b;
int c;
cin>>a>>b>>c;
if(!mp.count(a)) mp[a]=++tot;
if(!mp.count(b)) mp[b]=++tot;
q[i] = (node){mp[a],mp[b],c };
}
ll res=0;
int cnt=0;
sort(q,q+m);
for(int i=0;i<m;i++){
int t1=find(q[i].a);
int t2=find(q[i].b);
if(t1!= t2) {
pre[t1]=t2;
res+=q[i].c;
cnt++;
}
}
if(cnt != n-1) puts("No!");
else printf("%lld\n",res);
}
return 0;
}
Prim算法求最小生成树
题目表述：
给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，
其中边的权值之和最小的生成树被称为无向图G的最小生成树。
输入输出格式：
输入格式
第一行包含两个整数n和m
接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6
$Kruskal$算法:
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=510;
int pre[N];
struct node{
int a,b,c;
bool operator<(const node& t)const{
return c<t.c;//要对权值排序用结构体重载
}
}s[N];
int find(int x){
if(x!=pre[x]) pre[x]=find(pre[x]);
return pre[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) pre[i]=i;
for(int i=1;i<=m;i++) {
cin>>s[i].a>>s[i].b>>s[i].c;
}
sort(s+1,s+1+m);
int sum=0,cnt=0;
for(int i=1;i<=m;i++){
int t1 = find(s[i].a);
int t2 = find(s[i].b);
if(t1 != t2 ) {//不能形成环
pre[t1]=t2;
sum+=s[i].c;
cnt++;
}
}
if(cnt==n-1 ) cout<<sum<<endl;//终止条件
else cout<<'impossible'<<endl;
return 0;
}
$Prim$算法:
#include <bits/stdc++.h>
using namespace std;
const int N=520;
const int INF=0x3f3f3f3f;
int pre[N];
int g[N][N];//邻接矩阵（记录边）
int dis[N];//权值
bool st[N];//该顶点是否已经加入最小生成树
int res,n,m;
int prim()
{
//若图不连通返回INF,否则返回res;
memset(dis,INF,sizeof(dis));
int res=0;
for(int i=0;i<n;i++)//迭代n次(而Dijkstra算法中为：for(int i=1;i<=n-1;i++))
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dis[j]<dis[t]))
{
t=j;
}
}
if(i&&dis[t]==INF) return INF;
if(i) res+=dis[t];
st[t]=true;
for(int j=1;j<=n;j++) dis[j]=min(dis[j],g[t][j]);
}
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) pre[i]=i;
memset(g,INF,sizeof(g));
for(int i=1;i<=m;i++) {
int a,b,c;
cin>>a>>b>>c;
g[a][b] =g[b][a] = min(g[a][b],c);
}
int ans=prim();
if(ans == INF) cout<<"impossible"<<endl;
else cout<<ans<<endl;
return 0;
}
(补充)：
