HDU 1233

缺乏、安全感 2022-08-21 11:58 11阅读 0赞

**畅通工程**

贪心最小生成树

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int a[10001];
    struct st
    {
    	int x,y,len;
    }s[100001];
    int find(int x)
    {
    	while(a[x]!=x)
    	{
    		x=a[x];
    	}
    	return x;
    }
    int un(int x,int y)
    {
    	x=find(x);
    	y=find(y);
    	if(x!=y)
    	{
    		a[x]=y;
    		return 1;
    	}
    	else
    	return 0;
    }
    int cmp(const void *a,const void *b)
    {
    	st c=*(st *)a;
    	st d=*(st *)b;
    	return c.len-d.len;
    }
    int main()
    {
    	int i,j,k,n,m,t,l,tt,t1,t2;
    	while(~scanf("%d",&n))
    	{
    		if(n==0)
    		break;
    		for(i=1;i<=10000;i++)
    		{
    			a[i]=i;
    		}
    		k=0;
    		for(i=0;i<n*(n-1)/2;i++)
    		{		
    			scanf("%d %d %d",&s[i].x,&s[i].y,&s[i].len);
    		}
    		qsort(s,n*(n-1)/2,sizeof(s[0]),cmp);
    		int  sum=0;
    		for(i=0;i<n*(n-1)/2;i++)
    		{
    			sum+=un(s[i].x,s[i].y)*s[i].len;
    		}
    		printf("%d\n",sum);
    	}	
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu 1233 还是畅通工程

hdu 1233 还是畅通工程 * 题意 * 题解 * 源代码 [传送门][Link 1] 题意给定n个村子，和每个村子之间的距...

深碍√TFBOYSˉ_/ 2024年04月17日 05:28/ 0 赞/ 67 阅读

相关 HDU 1233(最小生成树,并查集)

这里使用kruskal: include <cstring> include <cstdio> include <queue> u

野性酷女/ 2022年09月20日 11:28/ 0 赞/ 161 阅读

相关最小生成树（kruskal） hdu 1233

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1233][http_acm.hdu.edu.cn_showproblem.ph

野性酷女/ 2022年08月27日 10:46/ 0 赞/ 193 阅读

相关 HDU 1233

畅通工程贪心最小生成树 include<stdio.h> include<string.h> include<algorithm>

缺乏、安全感/ 2022年08月21日 11:58/ 0 赞/ 12 阅读

相关还是畅通工程 hdu acm 1233 c++

还是畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

爱被打了一巴掌/ 2022年08月11日 04:29/ 0 赞/ 182 阅读

相关 HDU - 1233 - 还是畅通工程

-------------------- 题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=1233][http_acm.hdu

妖狐艹你老母/ 2022年06月10日 00:51/ 0 赞/ 171 阅读

相关 hdu 1233 还是畅通工程 kruskal

还是畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

清疚/ 2022年06月08日 00:59/ 0 赞/ 180 阅读

相关 HDU - 1233-还是畅通工程

HDU - 1233-还是畅通工程某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以

桃扇骨/ 2022年06月07日 12:25/ 0 赞/ 177 阅读

相关 HDU1233 还是畅通工程

<table> <tbody> <tr> <td> <div> <span style="margin-right:20px;"></s

末蓝、/ 2022年05月28日 00:53/ 0 赞/ 175 阅读

相关 HDU - 1233 还是畅通工程

还是畅通工程 Problem Description 某省调查乡村交通状况，得到的

谁借莪１个温暖的怀抱￠/ 2022年05月17日 05:44/ 0 赞/ 175 阅读