不详解模板--最小生成树 Kruskal 算法
最小生成树是由n个节点的连通图变化来的。这棵树满足如下条件：
1、是原来图的子图（原来的图扣去了几条边）
2、在保证图仍然连通的情况下，剩下的边权和是最小的
3、满足树的性质
最小生成树常用来解决这样的问题：
有n个村庄，他们之间本没有路（走的人多了就有路了 逃ε=ε=ε=┏(゜ロ゜;)┛）。我们现在知道每两个村庄之间修路的费用，求最少的修路费用。要求修路后任意两个村庄均可到达。
Kruskal 算法
很容易想到，1、我们希望取的边权（路费）要尽量小（贪心）。
2、如果a和b之间修了一条路，b和c之间修了一条路，那么我们就不必再在a和c之间修路了（所以满足树的性质）。
所以，我们从权值最小的边开始枚举（sort），将它连通的点标记为连通（放到同一个并查集中）。如果有两点已经连通（a->b->c 即视为a与c连通），跳过这条边，继续向后枚举。
如果不连接较短边而通过更长的边连接，一定不会比连接更短边更优。。。
关于并查集的知识，请。。。百度
贪心算法请感性理解。。。（逃）
不扯了，上代码：
//自我感觉码风良好（滑稽）
//应该比较易懂，变量名大都与含义对应，
//本代码耗时比较多
//PS：AC是肯定能AC的（luogu P3366)
//多说一句，这个题所有的点都连通。。。顺便标注一下易错点
#include <cstdio>
#include <algorithm>
using namespace std;
//Definition
const int MAXN = 5005;
const int MAXM = 400005;
struct Edge {
int from, to, val;
}edge;
int num_edge, n, m, ans;
int x, y, z;
int f;
inline void AddEdge(int from, int to, int val);
inline int getfather(int x);
inline void merge_set(int x, int y);
bool comp(const Edge a, const Edge b);
//main function
int main() {
scanf("%d%d", &n, &m); //注意取址符
for(int i = 1; i <= n; i++) f = i;
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &x, &y, &z); //无向图 从x到y有一条长度为z的边
AddEdge(x, y, z); //无向图
AddEdge(y, x, z); //无向图 有向图请去掉这一句
}
sort(edge, edge + num_edge, comp);//这很Kruskal QwQ 不要忘记std
for(int i = 0; i < num_edge; i++) {
int from = edge.from;
int to = edge.to;
int val = edge.val;
if(getfather(from) == getfather(to)) continue;//这两点已经在同一个并查集中
merge_set(from, to); //合并from和to所在的集合
ans += val;
}
printf("%d", ans);
return 0;
}
inline void AddEdge(int from, int to, int val) { //顾名思义，简单粗暴
edge.from = from;
edge.to = to;
edge.val = val;
num_edge++;
}
inline int getfather(int x) { //顾名思义
if(f == x) return x; //路径压缩
f = getfather(f);
return f;
}
inline void merge_set(int x, int y) { //合并两个并查集
int fx = getfather(x); //没有打按秩合并QwQ
int fy = getfather(y);
f = f; //不要把fx和fy打成x和y（我就这么干过）
}
bool comp(const Edge a, const Edge b) {
return (a.val < b.val);
}
页:
[1]