最优布线问题（最小生成树）

1231 最优布线问题

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 白银 Silver

题解

 

 

 

题目描述  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

2

数据范围及提示  Data Size & Hint

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

分类标签 Tags 点此展开 

 

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

 

代码：

#include<stdio.h>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100001
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}
int x,y,z,n,m,fa[N],tot;
long long ans;
struct Edge
{
    int x,y,z;
}edge[N];
int cmp(Edge a,Edge b)
{
    return a.z<b.z;
}
int found(int x)
{
    return fa[x]==x?x:fa[x]=found(fa[x]);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        x=read(),y=read(),z=read();
        edge[i].x=x;
        edge[i].y=y;
        edge[i].z=z;
    }
    sort(edge+1,edge+1+m,cmp);
    for(int i=1;i<=n;i++)
     fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int fx=found(edge[i].x),fy=found(edge[i].y);
        if(fx!=fy)
        {
            tot++;
            ans+=edge[i].z;
            fa[fy]=fx;
            if(tot==n-1)
              break;
        }
    }
    cout<<ans;
    return 0;    
}