最小生成树--Kruskal算法不详解
最小生成树
是由n个节点的连通图变化来的。这棵树满足如下条件：
1、是原来图的子图（原来的图扣去了几条边）
2、在保证图仍然连通的情况下，剩下的边权和是最小的
3、满足树的性质
最小生成树常用来解决这样的问题：
有n个村庄，他们之间本没有路（走的人多了就有路了）。我们现在知道每两个村庄之间修路的费用，求最少的修路费用。要求修路后任意两个村庄均可到达。
Kruskal 算法
很容易想到，1、我们希望取的边权（路费）要尽量小（贪心）。
2、如果a和b之间修了一条路，b和c之间修了一条路，那么我们就不必再在a和c之间修路了（所以满足树的性质）。
所以，我们从权值最小的边开始枚举（sort），将它连通的点标记为连通（放到同一个并查集中）。如果有两点已经连通（a->b->c 即视为a与c连通），跳过这条边，继续向后枚举。
如果不连接较短边而通过更长的边连接，一定不会比连接更短边更优。。。
贪心算法请感性理解。。。（逃ε=ε=ε=┏(゜ロ゜;)┛）
不扯了，上代码：
1 //自我感觉码风良好（滑稽）
2 //应该比较易懂，变量名大都与含义对应，不过耗时较多
3 //PS：AC是肯定能AC的（luogu P3366)
4 //多说一句，这个题所有的点都连通。。。
5
6 #include <cstdio>
7 #include <algorithm>
8
9 using namespace std;
10
11 const int MAXN = 5005;
12 const int MAXM = 400005;
13
14 struct Edge {
15 int from, to, val;
16 }edge[MAXM];
17
18 int num_edge, n, m, ans;
19 int x, y, z;
20 int f[MAXN];
21
22 inline void AddEdge(int from, int to, int val);
23 inline int getfather(int x);
24 inline void merge_set(int x, int y);
25 bool comp(const Edge a, const Edge b);
26
27
28 int main() {
29 scanf("%d%d", &n, &m);
30 for(int i = 1; i <= n; i++) f[i] = i;
31 for(int i = 0; i < m; i++) {
32 scanf("%d%d%d", &x, &y, &z); //无向图 从x到y有一条长度为z的边
33 AddEdge(x, y, z); //无向图
34 AddEdge(y, x, z); //无向图
35 }
36
37 sort(edge, edge + num_edge, comp); //这很Kruskal QwQ
38
39 for(int i = 0; i < num_edge; i++) {
40 int from = edge[i].from;
41 int to = edge[i].to;
42 int val = edge[i].val;
43 if(getfather(from) == getfather(to)) continue; //这两点已经在同一个并查集中
44 merge_set(from, to);
45 ans += val;
46 }
47 printf("%d", ans);
48 return 0;
49 }
50
51
52 inline void AddEdge(int from, int to, int val) { //顾名思义
53 edge[num_edge].from = from;
54 edge[num_edge].to = to;
55 edge[num_edge].val = val;
56 num_edge++;
57 }
58
59
60 inline int getfather(int x) { //顾名思义
61 if(f[x] == x) return x; //路径压缩
62 f[x] = getfather(f[x]);
63 return f[x];
64 }
65
66 inline void merge_set(int x, int y) { //合并两个并查集
67 int fx = getfather(x); //没有打按秩合并QwQ
68 int fy = getfather(y);
69 f[fx] = f[fy];
70 }
71
72 bool comp(const Edge a, const Edge b) {
73 return (a.val < b.val);
74 }
就酱。
版权声明：本文为fatsky原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。