题目：

思路：

有两种做法，一种是Prim算法，另外一种则是我所使用的Kruskal算法，Kruskal的算法实现可以参考：最小生成树-Prim算法和Kruskal算法，讲的已经是十分清楚了。

具体算法实现：

1.首先用结构体数组存储输入的边，并且初始化一个并查集思想中的父亲数组fa[i]；

2.用sort根据边权进行排序，边权小的边在前，大的在后；

3.从1到m遍历已经排好序的边

(1)遍历到边i，其两个节点分别是a和b，查找两个节点的祖先A和B

(2)如果A == B，加入边i会形成环路，则跳过该边，continue。

(3)如果A != B，进行祖先之间的Union：执行 fa[A] = B 或者 fa[B] = A，之后进行计数器的自增以及最小生成树长度的记录。

4.当加入的边为n-1条时(通过计数器反映)，结束循环。

其中非常需要注意的一点是，并查集的合并，指的是祖先之间的合并。

代码

//

//  main.cpp

//  Kruskal

//

//  Created by wasdns on 16/12/22.

//  Copyright © 2016年 wasdns. All rights reserved.

//

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

struct stedge

{

    int u, v, len;

};

bool cmp(stedge s1, stedge s2)

{

    return s1.len < s2.len;

}

stedge seg[100000];

int fa[100005];

void Inifa(int n)

{

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

    {

        fa[i] = i;

    }

}

int findfa(int x)

{

    int f = x;

    while (f != fa[f])

    {

        f = fa[f];

    }

    int i = x, j;

    while (i != f)

    {

        j = fa[i];

        fa[i] = f;

        i = j;

    }

    return f;

}

int main()

{

    int i, n, m;

    cin >> n >> m;

    Inifa(n);

    int u, v, w;

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

    {

        cin >> u >> v >> w;

        seg[i].u = u;

        seg[i].v = v;

        seg[i].len = w;

    }

    sort(seg+1, seg+m+1, cmp);

    int cnt = 0, lencnt = 0;

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

    {

        int fa1 = findfa(seg[i].u);

        int fa2 = findfa(seg[i].v);

        if (fa1 == fa2) continue;

        cnt++;

        lencnt += seg[i].len;

        fa[fa1] = fa2;         //一定是祖先找祖先合并

        if (cnt == n-1) break;

    }

    cout << lencnt;

    return 0;

}

/*

 4

 6

 1 2 1

 2 3 2

 1 3 3

 2 4 3

 3 4 5

 1 4 4

 */

2016/12/22

巴特西

DS实验题 PlayGame Kruskal(UnionFindSet)

题目：

思路：

代码

最新文章

热门文章