Noob Dream

 找回密码
 加入我们[Register]
搜索
查看: 106|回复: 0

最小生成树(kruskal算法)

[复制链接]

4

主题

4

帖子

73

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
73
发表于 2018-5-6 20:10:41 | 显示全部楼层 |阅读模式
kruskal适用于稀疏图
复杂度O(Elog(E))

[C++] 纯文本查看 复制代码
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;

const int maxn = 105;
#define INF 0x3f3f3f3f

struct node {
    int u;
    int v;
    int w;
}edge[maxn];

int cmp(node A, node B) {
    if (A.w < B.w) return 1;
    else return 0;
}
int fa[maxn];

int find(int x) {
    if (x == fa[x]) return x;
    fa[x] = find(fa[x]);
    return fa[x];
}

int main(){
        int N , M;
        while(scanf("%d%d",&N ,&M) != EOF){
        if (N == 0) break;
        for (int i = 1; i <= M; i++)
            fa[i] = i;
                for(int i = 0;i < N;i++) {
            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
                }
                sort(edge, edge + N, cmp);
        long long int sum = 0;
        int total = 0;
        for (int i = 0; i < N; i++) {
            int fx = find(edge[i].u);
            int fy = find(edge[i].v);
            if (fx != fy) {
                fa[fx] = fy;
                sum += edge[i].w;
                total++;
            }
        }
        if (total == M - 1) printf("%lld\n", sum);
        else printf("?\n");
        }
        return 0;
}

回复

使用道具 举报

本版积分规则

QQ|Noob Dream

GMT+8, 2018-8-15 12:53 , Processed in 0.123666 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表