hiho - 1098 最小生成树二·Kruscal算法

蔚落 2022-05-18 07:06 177阅读 0赞

#                               最小生成树二·Kruscal算法 #

### 描述 ###

随着小Hi拥有城市数目的增加，在之间所使用的Prim算法已经无法继续使用了——但是幸运的是，经过计算机的分析，小Hi已经筛选出了一些比较适合建造道路的路线，这个数量并没有特别的大。

所以问题变成了——小Hi现在手上拥有N座城市，且已知其中一些城市间建造道路的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。

[提示：积累的好处在于可以可以随时从自己的知识库中提取想要的！][Link 1]

### 输入 ###

每个测试点（输入文件）有且仅有一组测试数据。

在一组测试数据中：

第1行为2个整数N、M，表示小Hi拥有的城市数量和小Hi筛选出路线的条数。

接下来的M行，每行描述一条路线，其中第i行为3个整数N1\_i, N2\_i, V\_i，分别表示这条路线的两个端点和在这条路线上建造道路的费用。

对于100%的数据，满足N<=10^5, M<=10^6，于任意i满足1<=N1\_i, N2\_i<=N, N1\_i≠N2\_i, 1<=V\_i<=10^3.

对于100%的数据，满足一定存在一种方案，使得任意两座城市都可以互相到达。

### 输出 ###

对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。

### 样例输入 ###

5 29
    1 2 674
    2 3 249
    3 4 672
    4 5 933
    1 2 788
    3 4 147
    2 4 504
    3 4 38
    1 3 65
    3 5 6
    1 5 865
    1 3 590
    1 4 682
    2 4 227
    2 4 636
    1 4 312
    1 3 143
    2 5 158
    2 3 516
    3 5 102
    1 5 605
    1 4 99
    4 5 224
    2 4 198
    3 5 894
    1 5 845
    3 4 7
    2 4 14
    1 4 185

### 样例输出 ###

**题意描述：**

求出最小生成树。

**解题思路：**  
最小生成树模板题。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int f[100010];
    struct nate
    {
    	int x;
    	int y;
    	int z;
    }q[1000010];
    int cmp(struct nate a,struct nate b)
    {
    		return a.z<b.z;
    }
    int get(int i)
    {
    	if(f[i]==i)
    		return i;
    	else
    	{
    		f[i]=get(f[i]);
    		return f[i];
    	}
    }
    int merge(int u,int v)
    {
    	int t1,t2;
    	t1=get(u);
    	t2=get(v);
    	if(t1!=t2)
    	{
    		f[t2]=t1;
    		return 1;
    	}
    	return 0;
    }
    int main()
    {
    	int i,j,n,m,count,sum;
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{
    		for(i=1;i<=m;i++)
    			scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
    		sort(q+1,q+m+1,cmp);
    		count=0;
    		sum=0;
    		for(i=1;i<=n;i++)
    			f[i]=i;
    		for(i=1;i<=m;i++)
    		{
    			if(merge(q[i].x,q[i].y)==1)
    			{
    				count++;
    				sum=sum+q[i].z;
    			}
    			if(count==n-1)
    				break;
    		}
    		printf("%d\n",sum);
    	}
    	return 0;
    }

[Link 1]: http://hihocoder.com/problemset/problem/1098#