1231 最优布线问题 kruskal

骑猪看日落 2022-06-15 03:46 185阅读 0赞

题目描述 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类型来保存

#include<iostream>
    #include<algorithm>
    #include<string.h>
    #define MAX 100010 
    using namespace std;
    typedef long long LL;
    LL n,m,f[MAX],sum=0;
    struct st
    {
    	int s;
    	int e;
    	int w;
    }edge[MAX];
    void init()
    {
    	for (int i=1; i<=n; i++)
    	{
    		f[i] = i;
    	}
    }
    bool cmp(const st x, const st y)
    {
    	return x.w < y.w;
    }
    //查 
    int find(int x)
    {
    	if (f[x] != x)
    	{
    		f[x] = find(f[x]);
    	}
    	return f[x];
    }
    //并 
    void union_set(int x, int y)
    {
    	int xx = find(x);
    	int yy = find(y);
    	if(xx != yy){
    		f[xx] = yy;
    	}
    }
    void kruskal()
    {
    	int k=0;
    	//假如起点和终点不是在一个集合 ，那么将他们并入集合，加上权值 
    	for (int i=1; i<=m; i++)
    	{
    		if (find(edge[i].s) != find(edge[i].e))
    		{
    			union_set(edge[i].s,edge[i].e);
    			sum += edge[i].w;
    			k++;
    		}
    		//到达n-1条边就达到目的 
    		else if (k == n-1)
    		{
    			break;
    		}
    	}
    }
    int main()
    {
    	int a,b,c;
    	cin>>n>>m;
    	for (int i= 1; i<=m; i++)
    	{
    		cin>>a>>b>>c;
    		edge[i].s = a;
    		edge[i].e = b;
    		edge[i].w = c; 
    	}
    	//初始化并查集 
    	init();
    	sort(edge+1, edge+m+1, cmp);
    	
    	kruskal();
    	cout<<sum;
    	return 0;
    }