克鲁斯卡尔算法

克鲁斯卡尔算法(Kruskal算法)求最小生成树

题目传送：https://loj.ac/p/10065

1、排序函数sort，任何一种排序算法都行，下面的示例代码中，我采用的是冒泡排序算法

2、寻源函数getRoot，寻找某一个点在并查集中的根，注意，是根，不是双亲！，所以，判断的条件为如果某一个下标的值就是其本身，设a为并查集数组，v为数组值，如果a[v] = v，它就是根，否则就让v = a[v]，向上寻找，直到其相等。

1图的存储结构(a，b为边的两个顶点，w为边的权值),初始化

2.排序sort函数（按照权值从小到大）

3.getRoot寻源函数（v为并查集，x为待查顶点）

4.for循环遍历

 1 #include <bits/stdc++.h>

 2 using namespace std;

 3 #define x first

 4 #define y second

 5 const int mx= 250100;

 6 int n,k;

 7 typedef pair<int,int> PII;

 8 struct node{

 9     int x,y;

10     double z;

11 };

12 bool operator <(node &a,node &b)

13 {

14     return a.z<b.z;

15 }

16

17 int f[mx];

18 PII q[mx];

19 node edge[mx];

20

21 int get(int x)

22 {

23     return x==f[x]?x:get(f[x]);

24 }

25

26 double getdist(PII a,PII b)

27 {

28     int dx=a.x-b.x;

29     int dy=a.y-b.y;

30     return sqrt(dx*dx+dy*dy);

31 }

32

33 int main()

34 {

35     cin>>n>>k;

36     for(int i=1;i<=n;i++)

37     {

38         cin>>q[i].x>>q[i].y;

39     }

40     int m=0;

41     for(int i=1;i<=n;i++)

42     {

43         for(int j=1;j<=i;j++)

44         {

45             edge[++m].x=i;

46             edge[m].y=j;

47             edge[m].z=getdist(q[i],q[j]);

48         }

49     }

50     sort(edge+1,edge+1+m);

51     for(int i=1;i<=m;i++) f[i]=i;

52     int cnt=n;

53     double ans=0;

54     for(int i=1;i<=m;i++)

55     {

56         if(cnt<=k) break;

57         int a=get(edge[i].x),b=get(edge[i].y);

58         double w=edge[i].z;

59         if(a!=b)

60         {

61             f[a]=b;

62             cnt--;

63             ans=w;

64         }

65      }

66      printf("%.2lf\n",ans);

67 }