最小生成树--克鲁斯卡尔算法-蒲公英云

最小生成树--克鲁斯卡尔算法

算法描述：

          假设连通网N=（V,\{ E \}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，\{ \}），图中每一个顶点自成一个连通分量。
          在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边 选择下一条代价最小的边。
          以此类推，直至T中所有的顶点都在同一连通分量为止。

代码实现：

Java Code

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

#include <stdio.h>

#include <algorithm>

using namespace std;

#define inf 0x3fffffff

struct node

{


int
a,b,cost;
}c[
125000
];

int
fa[
505
],v;
bool cmp(node x,node y)
{

return
x.cost<y.cost;
}

void
init()
{

for
(
int
i=
1
;i<=v;i++)
    fa[i]=i;
}

int
find(
int
x)
{

if
(fa[x]!=x)
    fa[x]=find(fa[x]);

return
fa[x];
}

int
main()
{

int
t,e,x,y,sum,min;
    scanf(
“%d”
,&t);

while
(t—)
    {
        sum=
0
,min=inf;
        scanf(
“%d %d”
,&v,&e);
        init();

for
(
int
i=
0
;i<e;i++)
        scanf(
“%d %d %d”
,&c[i].a,&c[i].b,&c[i].cost);


for
(
int
i=
1
;i<=v;i++)
        {
            scanf(
“%d”
,&x);

if
(x<min)
            min=x;
        }

        sort(c,c+e,cmp);


for
(
int
i=
0
;i<e;i++)
        {
            x=find(c[i].a);
            y=find(c[i].b);

if
(x!=y)
            fa[x]=y,sum+=c[i].cost;
        }
        printf(
“%d\n”
,sum+min);
    }

return

0
;
}