kuangbin 最小生成树专题 - POJ - 1251 Jungle Roads （Kruskal算法 模板题）

Kruskal算法（稀疏图）
基本思路：
① 将所有边按权重从小到大排序 时间复杂度 $O(mlogm)$
② （并查集思想）
枚举每条边 u — v，权重是w。
如果u，v不连通，将这条边加到集合中
只需要存边即可，不需要存邻接矩阵和邻接表

附上模板

int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组struct Edge     // 存储边
{
    int a, b, w;
}edges[M];bool cmp(node a, node b) {
    return a.w < b.w;
}int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);return p[x];
}int kruskal()
{
    sort(edges, edges + m, cmp);// 初始化并查集for (int i = 1; i <= n; i ++ ) p[i] = i;int res = 0, cnt = 0;for (int i = 0; i < m; i ++ ){
    int a = edges[i].a, b = edges[i].b, w = edges[i].w;a = find(a), b = find(b);// 如果两个连通块不连通，则将这两个连通块合并if (a != b) {
    p[a] = b;res += w;cnt ++ ;}}//如果数量少于n - 1条边if (cnt < n - 1) return inf;return res;
}

Kruskal算法 模板题，用了并查集的思想，思路在上面
???

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
//#define int ll
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
    int w = 1, s = 0;char ch = getchar();while (ch < '0' || ch>'9') {
     if (ch == '-') w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') {
     s = s * 10 + ch - '0';    ch = getchar(); }return s * w;
//最大公约数
}int gcd(int x,int y) {
    if(x<y) swap(x,y);//很多人会遗忘，大数在前小数在后//递归终止条件千万不要漏了，辗转相除法return x % y ? gcd(y, x % y) : y;
}
int lcm(int x,int y)//计算x和y的最小公倍数
{
    return x * y / gcd(x, y);//使用公式
}
//------------------------ 以上是我常用模板与刷题几乎无关 ------------------------//
const int N = 110;
int n,cnt,flag;
int p[N];
struct node {
    int u, v, w;
} edges[N];bool cmp(node a, node b) {
    return a.w < b.w;
}
//返回x的祖宗节点+路径压缩
int find(int x)
{
    if (p[x] != x)p[x] = find(p[x]);return p[x];
}
//集合合并
void join(int a,int b)
{
    if(find(a) != find(b)) {
    p[find(b)] = find(a);cnt++;	flag = 1;} 
}
int main()
{
    while (~scanf("%d", &n) && n){
    int ans = 0;int sum = 0;cnt = 0;//初始化父节点for (int i = 1; i <= n; ++i)p[i] = i;for (int i = 1; i < n; ++i) {
    char a;int b;cin >> a >> b;while (b--) {
    edges[ans].u = i;char c;cin >> c;edges[ans].v = c - 'A' + 1;cin >> edges[ans++].w;}}//按权重从小到大排序sort(edges, edges + ans, cmp);//合并for (int i = 0; i < ans; ++i) {
    flag = 0;join(edges[i].u, edges[i].v);if (flag)sum += edges[i].w;}if (cnt == n - 1)printf("%d\n", sum);}return 0;
}