『最小生成树』最小生成树模板

学习最小生成树前提须知

最小生成树是指一个(n)个节点的图，让其变成一个仅有(n-1)个边且改变后该图是一张连通图，并且该图最终成为了一棵最小权重生成树 （小权值边尽可能留下，大权值边尽可能删除）或 最大权重生成树 （与前者相反）

算法内容

竞赛需要用到的点

1、最小生成树多用于其他算法的过渡使用，不单独考（xx不要纠结为什么每次都是这一句

2、可用于一种特殊的模板内（即有些边自始至终都不会用到的这种）

最小生成树略讲

最小生成树也是一个很简单的数据结构，它分了三种比较基本的算法 Kruskal 算法 Prim 算法 Boruvka 算法 ，这三个算法各有各的优缺点，其中 Boruvka 算法 在这三个算法中可以算是最优的算法，甚至可以因为 Boruvka 算法 的特性卡掉其他两个算法，但这不是我们的重点，先讲一下 Kruskal 算法 其他两个算法以后再来填坑（xxx 反正Noip之前应该不会了

Kruskal 算法 是基于 并查集算法 而进行的，很简单的思路就是，对一张图，将所有的边都拆出来，然后对每条边的边权进行排序（从大到小，从小到大看题目需要），然后再将边连回去，连边的时候判断两个点是否被连通了，如果是连通的，那么就将该边扔了再看下一条边，如果没有被连通，那么就将该条边连上，然后用并查集合并即可

那么根据上面信息我们就能够写出代码了

Kruskal 部分代码展现

//#define fre yes

#include <cstdio>

const int N = 100005;
struct Node {
    int x, y, z;
} kru[N];
int par[N];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        par[i] = i;
    } //起始化
}

int find(int x) {
    if(par[x] == x) return par[x];
    else return par[x] = find(par[x]);
} //并查集 看两点是否在同一个图内

bool cmp(Node x, Node y) {
    return x.z < y.z; //看情况修改 优先级给小边权还是大边权
}

int main() {
	...
    for (int i = 1; i <= n; i++) {
        scanf....
        kru[i].x = x;
        kru[i].y = y;
        ...
    }
    
    std::sort(kru + 1, kru + 1 + n, cmp);
    
    for (int i = 1; i <= m; i++) {
        int x = find(kru[i].x);
        int y = find(kru[i].y);
        if(x == y) continue ;
        //并查集合并操作，看是否在同一个图内 如果在就跳过 不在就合并
        par[x] = y;
        tot++; //这里是判断最后是否连通
    } if(tot == p - 1) ... //(p是点的个数)
}

若你想将处理之后的图转换到邻接表中怎么办？

const int N = 200005;
int head[N << 1], to[N << 1], ver[N << 1], edge[N << 1];

int tot;
void addedge(int x, int y, int z) {
    ver[tot] = y;
    edge[tot] = z;
    to[tot] = head[x];
    head[x] = tot++;
}

for (int i = 1; i <= m; i++) {
    int x = find(kru[i].x);
    int y = find(kru[i].y);
    if(x == y) continue ;
    par[x] = y;
    
    addedge(kru[i].x, kru[i].y, kru[i].z);
   	addedge(kru[i].y, kru[i].x, kru[i].z);
}

这就完成了

完整代码参考LuoGu P3366

//#define fre yes

#include <cstdio>
#include <algorithm>

const int N = 1000005;
struct Node {
    int x, y, z;
} edge[N];

int par[N];

void init(int n) {
    for (int i = 0; i <= n; i++) {
        par[i] = i;
    }
}

bool cmp(Node x, Node y) {
    return x.z < y.z;
}

int find(int x) {
    if(x == par[x]) return par[x];
    else return par[x] = find(par[x]);
}

int tot, ans;
int main() {
    static int n, m;
    scanf("%d %d", &n, &m);
    init(n);
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        edge[i].x = x;
        edge[i].y = y;
        edge[i].z = z;
    }

    std::sort(edge + 1, edge + 1 + m, cmp);

    for (int i = 1; i <= m; i++) {
        int x = find(edge[i].x);
        int y = find(edge[i].y);
        if(x == y) continue ;

        tot++;
        par[x] = y;
        ans += edge[i].z;
    } if(tot < n - 1) puts("orz");
    else printf("%d
", ans);
    return 0;
}