11-03最小生成树
最小生成树
一、定义
在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得联通所有结点的的 w(T) 最小，则此 T 为 G 的最小生成树。 w(t) = $\sum_{(u,v)∈t}$w(u,v)最小生成树是最小权值生成树的简称
二、算法Kruskal原理
假设给出了含有n个顶点的连通图，边有若干条，带有自己的权值。1.先构建一个只含有n个顶点，边集为空的子图
2.按照边权大小进行排序，多数从小到大排序
3.按顺序依次选取边，判断两端点是否已经同属于一个集合(并查集)一个集合则不选取该边，非一个集合选取该边
4.直到将所有边选完，合并n-1次即可连通，且因为是排序后从小到大进行的选择，将不会有更优的选择，即可求出最小生成树
三、模板代码实现
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e3 + 10, M = 2e5 + 10;
int n, m, cnt, sum;
int f[N];
struct node {
int x, y, z;
}tr[M];
bool cmp(node u, node v) {
return u.z < v.z;
}
void init(int n) {
for (int i = 1; i <= n; i++)
f[i] = i;
}
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
f[x] = y;
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> tr[i].x >> tr[i].y >> tr[i].z;
}
sort(tr, tr + m, cmp);
init(n);
cnt = n, sum = 0;
for (int i = 0; i < m; i++) {
int x = tr[i].x;
int y = tr[i].y;
if (find(x) != find(y)) {
merge(x, y);
cnt--;
sum += tr[i].z;
}
}
if (cnt != 1) {
cout << "orz" << endl;
return 0;
}
cout << sum << endl;
return 0;
}
四、相关题
1.P2330 繁忙的都市【普及/提高-】
题意：
给出n，m，表示有n个交叉路口(顶点)，m条道路道路(带权边),以下给出m行，每行u，v，c，表示交叉路口u(顶点u)和交叉路口v(顶点v)之间有道路相连，分值为c，需要使得通过选边，使得任意两个交叉路口(顶点)可以互通,同时分值尽可能少，输出选择了几条路，分值最大的那条道路的分值思路：
最小生成树实现：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e3 + 10, M = 2e5 + 10;
int n, m, cnt, sum;
int f[N];
struct node {
int x, y, z;
}tr[M];
bool cmp(node u, node v) {
return u.z < v.z;
}
void init(int n) {
for (int i = 1; i <= n; i++)
f[i] = i;
}
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
f[x] = y;
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> tr[i].x >> tr[i].y >> tr[i].z;
}
sort(tr, tr + m, cmp);
init(n);
cnt = n, sum = 0;
for (int i = 0; i < m; i++) {
int x = tr[i].x;
int y = tr[i].y;
if (find(x) != find(y)) {
merge(x, y);
cnt--;
sum = tr[i].z;
}
}
cout << n - 1 << ' ' << sum << endl;
return 0;
}