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

fatsky

最小生成树
　　是由n个节点的连通图变化来的。这棵树满足如下条件：
　　　　1、是原来图的子图（原来的图扣去了几条边）
　　　　2、在保证图仍然连通的情况下，剩下的边权和是最小的
　　　　3、满足树的性质
　　最小生成树常用来解决这样的问题：
　　　　有n个村庄，他们之间本没有路（走的人多了就有路了 逃ε=ε=ε=┏(゜ロ゜;)┛）。我们现在知道每两个村庄之间修路的费用，求最少的修路费用。要求修路后任意两个村庄均可到达。
Kruskal 算法
　　很容易想到，1、我们希望取的边权（路费）要尽量小（贪心）。
　　　　　　　　2、如果a和b之间修了一条路，b和c之间修了一条路，那么我们就不必再在a和c之间修路了（所以满足树的性质）。
　　所以，我们从权值最小的边开始枚举（sort），将它连通的点标记为连通（放到同一个并查集中）。如果有两点已经连通（a->b->c 即视为a与c连通），跳过这条边，继续向后枚举。
　　如果不连接较短边而通过更长的边连接，一定不会比连接更短边更优。。。
　　关于并查集的知识，请。。。百度
　　贪心算法请感性理解。。。（逃）
　　不扯了，上代码：

1. //自我感觉码风良好（滑稽）
   
2. //应该比较易懂，变量名大都与含义对应，
   
3. //本代码耗时比较多   
   
4. //PS：AC是肯定能AC的（luogu P3366)
   
5. //多说一句，这个题所有的点都连通。。。顺便标注一下易错点
   
6. 
   
7. 
   
8. #include <cstdio>
   
9. #include <algorithm>
   
10. 
    
11. using namespace std;
    
12. //Definition
    
13. const int MAXN = 5005;
    
14. const int MAXM = 400005;
    
15. 
    
16. struct Edge {
    
17.      int from, to, val;
    
18. }edge[MAXM];
    
19. 
    
20. int num_edge, n, m, ans;
    
21. int x, y, z;
    
22. int f[MAXN];
    
23. 
    
24. inline void AddEdge(int from, int to, int val);
    
25. inline int getfather(int x);
    
26. inline void merge_set(int x, int y);
    
27. bool comp(const Edge a, const Edge b);
    
28. 
    
29. //main function
    
30. int main() {
    
31.      scanf("%d%d", &n, &m);　　　　　　　　//注意取址符
    
32.      for(int i = 1; i <= n; i++) f[i] = i;
    
33.      for(int i = 0; i < m; i++) {
    
34.          scanf("%d%d%d", &x, &y, &z);    //无向图    从x到y有一条长度为z的边
    
35.          AddEdge(x, y, z);               //无向图
    
36.          AddEdge(y, x, z);               //无向图　　 有向图请去掉这一句
    
37.      }
    
38. 
    
39.      sort(edge, edge + num_edge, comp);  //这很Kruskal QwQ　　不要忘记std
    
40. 
    
41.      for(int i = 0; i < num_edge; i++) {
    
42.          int from = edge[i].from;
    
43.          int to = edge[i].to;
    
44.          int val = edge[i].val;
    
45.          if(getfather(from) == getfather(to)) continue;  //这两点已经在同一个并查集中
    
46.          merge_set(from, to);　　　　　　　　　　　　　　　　　//合并from和to所在的集合
    
47.          ans += val;
    
48.      }
    
49.      printf("%d", ans);
    
50.      return 0;
    
51. }
    
52. 
    
53. 
    
54. inline void AddEdge(int from, int to, int val) {    //顾名思义，简单粗暴
    
55.      edge[num_edge].from = from;
    
56.      edge[num_edge].to = to;
    
57.      edge[num_edge].val = val;
    
58.      num_edge++;
    
59. }
    
60. 
    
61. 
    
62. inline int getfather(int x) {               //顾名思义
    
63.      if(f[x] == x) return x;                 //路径压缩
    
64.      f[x] = getfather(f[x]);
    
65.      return f[x];
    
66. }
    
67. 
    
68. inline void merge_set(int x, int y) {       //合并两个并查集
    
69.      int fx = getfather(x);                  //没有打按秩合并QwQ
    
70.      int fy = getfather(y);
    
71.      f[fx] = f[fy];　　　　　　　　　　　　　　　　//不要把fx和fy打成x和y（我就这么干过）
    
72. }
    
73. 
    
74. bool comp(const Edge a, const Edge b) {
    
75.      return (a.val < b.val);
    
76. }
    

复制代码