nyoj38布线问题(最小生成树)_有关于你_XL的博客-程序员秘密_nyoj 布线问题

技术标签: 算法  C语言  nyoj  个人  

最小生成树算法有两个比较出名的,就是pime算法和krakusl算法。

首先说下krakusl算法。这个算法就是三个步骤,

第一,把每个顶点看成一个集合,边集按照权值大小排序。

第二,从最小的 边集开始,如果边的加入没有使得生成树成为环(并查集),则把该边加入生成树,否则,判断下一条边。

第三,当所有的顶点都加入了生成树,则所有加入的边构成最小生成树。

更加详细的请查找百度百科。

下面是我写的此题的代码。

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<string.h>
#include<algorithm>
#define min(a,b) a>b?b:a
using namespace std;
int L[502];
int father[502];
struct P{
	int val;
	int v1,v2;
}a[130000];
void work();
int v,e;
int sum;
int comp(const void *a,const void *b)
{
	P *c=(P *)a;
	P *d=(P *)b;
	return c->val-d->val;
}
int main()
{
	int T;	
	int i;
	scanf("%d",&T);
	while(T--)
	{
		memset(father,0,sizeof(father));
		scanf("%d%d",&v,&e);
		for(i=0;i<e;i++)
			scanf("%d %d %d",&a[i].v2,&a[i].v1,&a[i].val);
		for(i=0;i<v;i++)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
			scanf("%d",&L[i]);
		sum=0;
		qsort(a,e,sizeof(a[0]),comp);
		work();
		printf("%d\n",sum+*min_element(L,L+v));
		
	}
	return 0;
}
int find(int x)//并查集函数
{
	if(x!=father[x]) father[x]=find(father[x]);
	return father[x];
}
void work()//kruskal算法
{
	int i;
	for(i=1;i<=v;i++)
		father[i]=i;
	for(i=0;i<e;i++)
	{
		int t=find(a[i].v1);
		int tt=find(a[i].v2);
		if(t!=tt)
		{
			sum+=a[i].val;
			father[t]=tt;
		}
	}	
}

这个算法也不是很理解,但是pime算法我也不太清楚,我写不出来,所以要想了解此算法,请移步 此处


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u012685794/article/details/40745207

智能推荐

Tomcat启动报错 org.apache.catalina.LifecycleException_再见残月的博客-程序员秘密

Tomcat启动报org.apache.catalina.LifecycleException错误,很大概率是xml文件配置错误:如上,&amp;lt;servlet&amp;gt;标签配置错误,报org.apache.catalina.LifecycleException错误,服务器无法启动再遇此类错误,可首先排查xml文件配置是否正确...

hive map格式转换为字符串_Hive:map字段存储和取用 ( str_to_map函数 )_在南极找不到南的博客-程序员秘密

str_to_map(字符串参数, 分隔符1, 分隔符2)使用两个分隔符将文本拆分为键值对。分隔符1将文本分成K-V对,分隔符2分割每个K-V对。对于分隔符1默认分隔符是 ',',对于分隔符2默认分隔符是 '='。例子:1. 创建map字段DROP TABLE IF EXISTS tmp.tmp_str_to_map;CREATE TABLE IF NOT EXISTS tmp.tmp_str_t...

leetcode算法题--求解两数之和(C语言实现)_Alfred king的博客-程序员秘密

题目描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。范例给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]思路分析:本题可以使用比较暴力的解法,通过嵌套循环,时间复杂度为O(X^2)去完成。实现代码:int* twoSum(

everything 使用技巧_溪谷者的博客-程序员秘密

everything与TC搭配使用 搜索结果的文件夹可以直接用TC打开命令:$exec(&quot;D:\源程序\7应用小程序\TotalCMD64\Totalcmd64.exe&quot; %1)

Google Chrome 浏览器快捷键说明大全_new_liu的博客-程序员秘密_chrome快捷键说明

标签页和窗口快捷键快捷键说明Ctrl + t打开新的标签页。(常用)Ctrl + Shift + Tab 或 Ctrl + Pgup跳转到上一个打开的标签页。(常用)Ctrl + 1 到 Ctrl + 8跳转到指定索引号的标签页。(常用)Alt + ←打开历史记录中的上一页。(常用)Alt + →打开历史记录中的下一页。(常用)Ctrl...

随便推点

express中res.sendFile、res.render、express.static()三者的使用_柒君的博客-程序员秘密_express sendfile

一、res.sendFile必须使用绝对路径,它的作用是响应出去一个文件,可以直接返回html文件做渲染。app.get("/kkk", (req, res) =&gt; { res.sendFile(path.resolve(__dirname,"./views/insertArticle.html"));});浏览器访问http://localhost:8000/kkk,其实就是在访问insertArticle.html文件。二、res.render使用这个方法就代表需要用到“模板引擎

搜索的两极------数据和用户为何缺一不可?_feitianhanxue的博客-程序员秘密

搜索的两极------数据和用户为何缺一不可?文/王易见    搜索因其海量数据、精准定位等特征在互联网领域创造了一个又一个的奇迹,无可否认,搜索的商业价值已经发挥到了一个比较高的程度,不过,这还只到了不足一半的程度。    搜索的两端分别为用户和数据,目前的搜索仅仅挖掘了数据的商业价值,而未能挖掘用户的商业价值,其实,如果论商业价值,用户并不低于数据,只是需要通过一个合理的途径

response对象和request对象_李墨瞳的博客-程序员秘密_request.response.bytelength

1. request 对象 和 response对象1.1. request 对象request 对象类型 , 继承自stream.Readablerequest 对象常用成员request.headersrequest.rawHeadersrequest.httpVersionrequest.methodrequest.url1.2. resp

VHDL实现全加器_失散多年的哥哥的博客-程序员秘密_vhdl全加器

VHDL实现全加器1.一位全加器全加器是能够计算低位进位的二进制加法电路,一位全加器(FA)的逻辑表达式为:F=A⊕B⊕CiCo=Ci(A⊕B)+AB其中A,B为要相加的数,Ci为进位输入;F为和,Co是进位输出真值表如下:原理图如下:因此在设计实体时,选定三输入二输出:LIBRARY IEEE;USE IEEE.STD_LOGIC_1164.ALL;USE IEEE.STD_LOGIC_UNSIGNED;ENTITY homework5 IS PORT( a,b,ci:

《如何撰写和发表SCI期刊论文》阅读笔记_不会vector的博客-程序员秘密

一.SCI论文的格式和整体构思现代的SCI论文的结构一般包括三个核心部分:引言(Introduction)、主体(Body)和讨论(Discussion)。目前,最常见的格式是IMRaD格式(Introduction,Method,Result and Discussion),这使读者能够按照合理的思路获取具体的信息,知道从稿件的哪个部分去了解某一特定结果。SCI论文的格式写作要点AbstractWhat did I do in a nutshell?Introduciton

计算机电缆的铜丝和铜带的区别,请问铜带屏蔽和铜丝屏蔽那个好? - 无图版_正直博的博客-程序员秘密

ashui1986 --- 2010-02-26 11:15:481各位大侠请问铜带屏蔽和铜丝屏蔽那个好??要是铜带屏蔽效果好,那为什么标准规定是 铜丝屏蔽这样的屏蔽形式不是单独使用 而采用缠绕+反向扎带这样的屏蔽形式??望各位大侠能够给予详细的赐教 谢谢!!![yyyfff 在 2010-2-26 11:48:00 编辑过]yyyfff --- 2010-02-26 11:54:442按屏蔽..._1671465600

推荐文章

热门文章

相关标签