codevs1231 最优布线问题

1231 最优布线问题

题目描述 Description

学校需要将n台计算机连接起来，不同的2台计算机之间的连接费用可能是不同的。为了节省费用，我们考虑采用间接数据传输结束，就是一台计算机可以间接地通过其他计算机实现和另外一台计算机连接。

为了使得任意两台计算机之间都是连通的（不管是直接还是间接的），需要在若干台计算机之间用网线直接连接，现在想使得总的连接费用最省，让你编程计算这个最小的费用。

输入描述 Input Description

输入第一行为两个整数n,m（2<=n<=100000，2<=m<=100000），表示计算机总数，和可以互相建立连接的连接个数。接下来m行，每行三个整数a,b,c 表示在机器a和机器b之间建立连接的话费是c。(题目保证一定存在可行的连通方案, 数据中可能存在权值不一样的重边，但是保证没有自环)

输出描述 Output Description

输出只有一行一个整数，表示最省的总连接费用。

样例输入 Sample Input

3 3

1 2 1

1 3 2

2 3 1

样例输出 Sample Output

数据范围及提示 Data Size & Hint

最终答案需要用long long类型来保存

分类标签 Tags 点此展开

最小生成树图论并查集树结构

最小生成树模板——Kruskal

#include<bits/stdc++.h>

#define LL long long
#define N 1000000
using namespace std;

int n,m,fa[N];
LL ans;
struct node{
    int u,v,w;
}e[N];

int find(int u){
    return fa[u]=fa[u]==u?u:find(fa[u]);
}

bool cmp(node A,node B){
    return A.w<B.w;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+1+m,cmp);
    int item=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int fx=find(e[i].u),fy=find(e[i].v);
        if(fx==fy) continue;
        fa[fx]=fy;ans+=e[i].w;++item;
        if(item==n-1) break;
    }
    printf("%lld",ans);
    return 0;
}