不详解模板--最小生成树 Kruskal 算法

fatsky

最小生成树
　　是由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[MAXM];
 
 int num_edge, n, m, ans;
 int x, y, z;
 int f[MAXN];
 
 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] = 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[i].from;
         int to = edge[i].to;
         int val = edge[i].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[num_edge].from = from;
     edge[num_edge].to = to;
     edge[num_edge].val = val;
     num_edge++;
 }
 
 
 inline int getfather(int x) {               //顾名思义
     if(f[x] == x) return x;                 //路径压缩
     f[x] = getfather(f[x]);
     return f[x];
 }
 
 inline void merge_set(int x, int y) {       //合并两个并查集
     int fx = getfather(x);                  //没有打按秩合并QwQ
     int fy = getfather(y);
     f[fx] = f[fy];　　　　　　　　　　　　　　　　//不要把fx和fy打成x和y（我就这么干过）
 }
 
 bool comp(const Edge a, const Edge b) {
     return (a.val < b.val);
 }