<学习笔记> 最小生成树 Kruskal

先来看看一般的问题：给你n个点，m条边，每条边都有一个边权，问你保留哪些边才能使n个点都互相连通同时边权和最小，求最小边权和。

不难想到只要要建一棵树（n-1条边），同时保证边权和最小。

kruskal算法：利用贪心的思想，把边按照边权从小到大排序，每次对于当前边，检查终点和起点是否连通，若不连通就加边，直到加到n-1条边为止。

最小生成树性质：任意两点之间的最短路径一定在最小生成树中，可以用反证法。

代码：codevs 1078 最小生成树

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 int N,cnt,k,Cnt,ans;
 9 int fa[110];
10 
11 struct maple{
12     int f,t,d;
13 }Rode[1000010]; 
14 
15 void Build(int f,int t,int d)
16 {
17     Rode[++cnt]=(maple){f,t,d};
18 }
19 int find(int x)
20 {
21     return fa[x]==x?x:fa[x]=find(fa[x]);
22 }
23 bool cmp(maple a,maple b)
24 {
25     return a.d<b.d;
26 }
27 
28 int main()
29 {
30     scanf("%d",&N);
31     for(int i=1;i<=N;++i)  fa[i]=i;
32     for(int i=1;i<=N;++i)
33        for(int j=1;j<=N;++j)
34        {
35               scanf("%d",&k);
36               if(i<j) Build(i,j,k);
37        }
38     sort(Rode+1,Rode+cnt+1,cmp);
39     for(int i=1;i<=cnt;++i)
40     {
41         int x=find(Rode[i].f),y=find(Rode[i].t);
42         if(x!=y)
43         {
44             ans+=Rode[i].d;
45             fa[x]=y;
46             ++Cnt;
47             if(Cnt==N-1) break;
48         }
49     }
50     printf("%d",ans);
51     return 0;
52 }