HDU 1233 还是畅通工程 (并查集)

╰半夏微凉° 2022-06-05 01:57 155阅读 0赞

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=10005; 
    struct node
    {
    	int f;
    	int l;
    	int len;
    }a[maxn];//定义一个结构体储存公路的信息 
    int n,m,b[maxn],ans;
    bool cmp(node a,node b)
    {
    	return a.len<b.len;//按公路的长度从小到大排序 
    }
    int find(int x)
    {
    	int r=x;
    	while(b[r]!=r)//寻找父节点 
    	r=b[r];//如果当前部位父节点则继续寻找 
    	return r;//返回父节点 
    }
    void mergy(int x,int y)
    {
    	int fx=find(x);
    	int fy=find(y);
    	if(fx!=fy)
    	b[fy]=x;//将父节点合并 
    }
    int kruskal()
    {
    	sort(a,a+m,cmp);//排序，优先查找长度小的 
    	for(int i=0;i<=n;i++)
    	b[i]=i;//给b数组赋值 
    	ans=0;//长度总和 
    	for(int i=0;i<m;i++)
    		if(find(a[i].f)!=find(a[i].l))//如果两个村子没有公路 
    		{
    			mergy(a[i].f,a[i].l);//查找父节点 
    			ans+=a[i].len;//长度相加	
    		}
    		return ans;
    }
    int main()
    {
    	while(scanf("%d",&n)!=EOF&&n!=0)
    	{
    		m=n*(n-1)/2;
    		for(int i=0;i<m;i++)
    		scanf("%d %d %d",&a[i].f,&a[i].l,&a[i].len);		
    		printf("%d\n",kruskal());
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 hdu 1233 还是畅通工程

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

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

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

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

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

相关 1233 还是畅通工程(kruskal)

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

朴灿烈づ我的快乐病毒、/ 2022年06月16日 00:53/ 0 赞/ 131 阅读

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

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

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

相关 hdu 1233 还是畅通工程 kruskal

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

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

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

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

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

相关 HDU 1233 还是畅通工程 (并查集)

include <bits/stdc++.h> using namespace std; const int maxn=10005; stru

╰半夏微凉°/ 2022年06月05日 01:57/ 0 赞/ 156 阅读

相关 HDU1233 还是畅通工程

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

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

相关 HUD1233“还是畅通工程”

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

水深无声/ 2022年05月19日 10:39/ 0 赞/ 130 阅读

相关 HDU - 1233 还是畅通工程

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

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