最小生成树
一、定义
在一给定的无向图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;
}
标签:11,03,cnt,node,int,sum,tr,最小,顶点
From: https://www.cnblogs.com/forleaves/p/17569642.html