最小生成树 （无向无环图）
概念
1.Prim算法 P3366 【模板】最小生成树 - 洛谷
邻接矩阵实现
#include<iostream>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10;
int dis[N]; //记录每个结点到其他结点的巨鹿
bool st[N];//记录每个节点是否被遍历过
int edge[N][N];//记录每个结点到其他结点的巨鹿
int n, m;
//prim算法实现
int prim()
{
//把dis初始化成无穷大
memset(dis, INF, sizeof(dis));
dis[1] = 0;//第一个结点开头
int ret = 0;
for (int i = 1; i <= n; i++)
{
int t = 0;
//找最近点
for (int j = 1; j <= n; j++)
{
if (!st[j] && dis[j] < dis[t])t = j;//更新最小值的下标
}
//判断是否联通
if (dis[t] == INF)return INF;
//把该点加进去
st[t] = true;
ret += dis[t];
//更新dis
for (int i = 1; i <= n; i++)
{
if (dis[i] > edge[t][i])//如果距离大于新的结点距离其他节点的距离，更新
dis[i] = edge[t][i];
}
}
return ret;
}
int main()
{
cin >> n >> m;
memset(edge, INF, sizeof(edge));
for (int i = 1; i <= m; i++)
{
int x, y, z; cin >> x >> y >> z;
//注意有重边的情况，注意是取笑，初始化为无穷大
edge[x][y] = edge[y][x] = min(edge[x][y], z);
}
int ret = prim();
if (ret == INF)cout << "orz" << endl;
else
cout << ret << endl;
}vector数组实现
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int, int> PII;//连接的点，权值
const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10;
int n, m;
int dis[N];
bool st[N];
vector<PII> dp[N];
int prim()
{
memset(dis, INF, sizeof(dis));
dis[1] = 0;
int ret = 0;
for (int i = 1; i <= n; i++)//加入n个点，功德圆满
{
//找最近的点
int t = 0;//dis[0]给初始化成INF了
for (int j = 1; j<= n; j++)
{
if (!st[j] && dis[j] < dis[t])//没有被访问过并且比t小，更新t
{
t = j;
}
}
//判断是否联通
if (dis[t] == INF)return INF;
st[t] = true;
ret += dis[t];
//更新dis
for (auto& x : dp[t])
{
int a = x.first;//相连的点
int b = x.second;//相连的点的权值
/*if (dis[a] > b)dis[a] = b;*/
dis[a] = min(dis[a], b);//这里可以解决重边的情况
}
}
return ret;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, z; cin >> x >> y >> z;
dp[x].push_back({ y,z });
dp[y].push_back({ x,z });
}
int ret = prim();
if (ret == INF)cout << "orz" << endl;
else
cout << ret << endl;
}2.克鲁斯卡尔算法（并查集实现）
P3366 【模板】最小生成树 - 洛谷
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5010;//点
const int M = 2e5 + 10;//边
const int INF = 0x3f3f3f3f;
struct node
{
int x, y, z;
}a[M];
int f[N];//并查集
int n, m;
int find(int x)
{
return f[x] == x ? x : f[x] = find(f[x]);
}
void un(int x, int y)
{
f[find(x)] = find(y);
}
bool cmp(node& x, node& y)
{
return x.z < y.z;
}
int kruskal()
{
int ret = 0;
int cnt = 0;
for (int i = 1; i <= m; i++)
{
int x = a[i].x, y = a[i].y, z = a[i].z;
if (find(x) != find(y))//没有并在一起，就整
{
cnt++;//记录边的个数，最小生成树，节点数n，边数n-1
ret += z;
un(x, y);
}
}
if (cnt != n-1)return INF;//成功的话是n - 1,没有说明不联通
return ret;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> a[i].x >> a[i].y >> a[i].z;
}
//并查集初始化
for (int i = 1; i <= n; i++)f[i] = i;
//排序，从小到大
sort(a + 1, a + 1 + m, cmp);
int ret = kruskal();
if (ret == INF)cout << "orz" << endl;
else
cout << ret << endl;
}
P1194 买礼物 - 洛谷
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 500*500+10;//结点*结点 == 边的个数，我们存的是边的个数
const int M = 1010;
int a, n;//A和节点数
int pos;//有几条边要存
int f[N];//并查集
struct node
{
int x, y, z;
}b[N];//存边之间的个数
bool cmp(node& x, node& y)//排序
{
return x.z < y.z;
}
int find(int x)
{
return f[x] == x ? x : f[x] = find(f[x]);
}
//克鲁斯卡尔算法
int kk()
{
int ret = 0;//总价
int cnt = 0;//几条边，用来计算分成几块，有几块就*多少个A
for (int i = 1; i <= pos; i++)
{
int x = b[i].x, y = b[i].y, z = b[i].z;//取出边的数据
int fx = find(x);
int fy = find(y);
if (fx != fy && z < a && z != 0)
{
ret += z;
cnt++;//计算有多少条边
f[find(x)] = find(y);//合并
}
}
ret += (n - cnt) * a;//有几块树
return ret;
}
int main()
{
cin >> a >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
int k; cin >> k;
//只需要存一条边的关系
//但其实就算不要也无所谓，因为并查集合并后，也不会要重复的
//克鲁斯卡尔算法只需要存取，边的数据就好了，不重复更好
if (i >= j)continue;
pos++;
b[pos].x = i, b[pos].y = j, b[pos].z = k;
}
}
for (int i = 1; i <= n; i++)f[i] = i;
sort(b + 1, b + 1 + pos,cmp);
int ret = kk();
cout << ret << endl;
}
P2330 [SCOI2005] 繁忙的都市 - 洛谷
瓶颈树：生成所有生成树中，最大边权值最小的那棵树。
也就是最小生成树。
最小生成树的最大边值也就是最终结果
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 310;
const int M = 8010;
int n, m;
int pos;
int f[N];
struct node
{
int x, y, z;
}a[M];
int find(int x)
{
return f[x] == x ? x : f[x] = find(f[x]);
}
bool cmp(node& x, node& y)
{
return x.z < y.z;
}
int ret = 0;
void kk()
{
for (int i = 1; i <= m; i++)
{
int x = a[i].x, y = a[i].y, z = a[i].z;
int fx = find(x), fy = find(y);
if (fx != fy)
{
ret = max(ret, z);
f[fx] = fy;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
a[i].x = x, a[i].y = y, a[i].z = z;
}
cout << n - 1 << " ";
for (int i = 1; i <= n; i++)f[i] = i;
sort(a + 1, a + 1 + m, cmp);
kk();
cout << ret << endl;
}P2573 [SCOI2012] 滑雪 - 洛谷
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const int M = 2e6 + 10;//考虑两重变
typedef pair<int, int> PII;//可以到的点，到该点的距离
int n, m;//n个景点，m条边
int h[N];//每个景点的高度
vector<PII> dp[N];//记录该点可以去的所有的点+到的距离
bool st[N];
LL cnt;//记录有多少个景点被访问了
int pos;//记录有多少条边
struct node
{
int x, y, z;
}a[M];//记录边的数据
int f[N];//并查集
void dfs(int u)//找所有可以到达的边
{
cnt++;
st[u] = true;
for (auto& s : dp[u])//遍历该点可以到达的每一条边，并且进行记录
{
int x = s.first, y = s.second;
++pos;//多一条边
a[pos].x = u, a[pos].y = x, a[pos].z = y;
if (!st[x])//没有被访问过
{
dfs(x);
}
}
}
bool cmp(node& x, node& y)//从该点到宁一个点的高的优先，其次是距离
{
int x1 = x.x, y1 = x.y, z1 = x.z;
int x2 = y.x, y2 = y.y, z2 = y.z;
if (h[y1] != h[y2])return h[y1] > h[y2];
return z1 < z2;
}
int find(int x)
{
return f[x] == x ? x : f[x] = find(f[x]);
}
LL ret;
void kk()
{
sort(a + 1, a + 1 + pos, cmp);
for (int i = 1; i <= n; i++)f[i] = i;
for (int i = 1; i <= pos; i++)
{
int x = a[i].x, y = a[i].y, z = a[i].z;
int fx = find(x);
int fy = find(y);
if (fx != fy)
{
ret += z;
f[fx] = fy;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> h[i];
for (int i = 1; i <= m; i++)
{
int x, y, z; cin >> x >> y >> z;
if (h[x] >= h[y])dp[x].push_back({ y,z });
if (h[y] >= h[x])dp[y].push_back({ x,z });//如果是 == 的话，那么两边的都要记录
}
dfs(1);
kk();
cout << cnt << " "<<ret << endl;
}
有向图：
由于克鲁斯卡尔算法要把所有的边进行排序没所以我们要创建一个起点,终点，边的结构体
题目没有明确给出那就自己创建。
dfs:把所有的路径都找到。（遍历到一条边就加入路径）
用胶囊把所有可以到的点统计到。->生成最小生成树。最小生成树：利用dfs找到的路径据生成最小生成树
距离最短->所有距离的总和。--->最小生成树。选边的时候，优先去往高的位置的边，其次才是距离