文档章节

Noi 题库 253:丛林中的路

机智的帝江
 机智的帝江
发布于 2016/10/30 09:00
字数 786
阅读 19
收藏 0

描述

输入图片说明

热带岛屿Lagrishan的首领现在面临一个问题:几年前,一批外援资金被用于维护村落之间的道路,但日益繁茂的丛林无情的侵蚀着村民的道路,导致道路维修开销巨大,长老会不得不放弃部分道路的维护。上图左侧图显示的是正在使用道路的简图以及每条路每个月的维修费用(单位为aacms)。现在长老会需要提出一种方案,即需要保证村落之间都可以互相到达,又要将每个月的道路维修费用控制在最小。村子编号为从A到I。上图右侧显示的方案最小维修开销为216 aacms每月。

输入 输入包含1~100个数据集,最后一行为0.每个数据集第一行为村落数目n, 1 < n < 27,依次用字母表的前n个字母标记。接下来有n-1行,每行的第一个数据便是按字母顺序排列的村子编号(不包括最后一个村庄)。每个村庄后面的数据k代表该村庄通往编号在其之后的村庄的道路数目,如A 2 B 12 I 25,代表A村庄有2个编号在A之后的村庄和其相连。若k大于0,k后面会依次给出这k个村庄的编号以及各自到起始村庄的道路维修费用,如A 2 B 12 I 25,代表A和B之间道路维修费用为12, A和I之间道路维修费用为25(维修费用为不超过100的正整数).路的总数目不超过75条,每个村庄到其他村庄不会有超过15条路(包括编号在其之前和之后的)。 输出 每个数据集有一个输出:针对解决方案每个月维修道路的小费用。 提示:蛮力算法虽能找出解决方案,但将会超出时间限制。 样例输入 9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0 样例输出 216 30

裸的最小生成树,没什么好说的。直接上代码

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

struct node
{
	int u,v,w;
}f[101];

bool cmp(node a,node b)
{
	return a.w<b.w;
}

int fa[101];

int find(int s)
{
	return fa[s]==s?s:fa[s]=find(fa[s]);
}

bool merge(int s,int t)
{
	int f1=find(s),f2=find(t);
	if (f1!=f2)
	{
		fa[f1]=f2;
		return 1;
	}
	return 0;
}

int solve(int n)
{
	for (int i=1;i<=n;i++) fa[i]=i;
	char t1,t2; int tot=0;
	for (int i=1;i<n;i++)
	{
		int num;
		cin>>t1>>num; 
		int tu=t1-'A'+1;
		for (int j=1;j<=num;j++)
		{
			int tw,tv;
			cin>>t2>>tw; tv=t2-'A'+1;
			f[++tot]=node{tu,tv,tw};
		}
	}
	sort(f+1,f+tot+1,cmp);
	int count=0,ans=0;
	for (int i=1;i<=tot;i++)
	{
		if (merge(f[i].u,f[i].v)) count++,ans+=f[i].w;
		if (count==n-1) break;
	}
	return ans;
}

int main()
{
	int n;
	while(cin>>n&&n!=0)
	cout<<solve(n)<<endl;
	return 0; 
}

© 著作权归作者所有

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
traceroute 节点查询

traceroute 調查連接到某部主機時,每個節點的連線速度 語法: 說明: - [root@test root]# traceroute [-i interface] [-g gateway] [host IP] - 參數說明: - -i :使用這個 interface 來連...

codetask
2016/12/24
15
0
全国青少年信息学奥林匹克竞赛系列活动简介

宗旨:旨在向那些在中学阶段学习的青少年普及计算机科学知识;给学校的信息技术教育课程提供动力和新的思路;给那些有才华的学生提供相互交流和学习的机会;通过竞赛和相关的活动培养和选拔优...

海天一树X
2018/09/07
0
0
摘抄一篇文章,特别后半段很值得大家看看。

我很少,CTRL C+V。更多时给出出处摘选。如下是全文COPY。哈。 ============= 掐尖不育苗让多数奥赛金牌得主难成大器 http://www.sina.com.cn 2012年08月07日 09:54 中国青年报   常州高级...

中山野鬼
2012/08/08
353
1
NCRE考试感想 四级嵌入式(上)

权威的官方文件 考试时间:2017年3月 经验写于:2017年5月 万事万物都在变化,四级嵌入式也是如此。所以,该经验仅作为参考,官方的文件才是权威。   考试时间与题目架构 考试时间为90min,...

志成就
05/26
59
0
小白程序员仅用 5 分钟入职 BAT,他只做了这件事!

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/csdnnews/article/details/88549362 有一个知名独立博客「左岸读书」,坚持运营11年。最为印象深刻的,是网站...

CSDN资讯
03/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Eureka应用注册与集群数据同步源码解析

在之前的EurekaClient自动装配及启动流程解析一文中我们提到过,在构造DiscoveryClient类时,会把自身注册到服务端,本文就来分析一下这个注册流程 客户端发起注册 boolean register() t...

Java学习录
24分钟前
5
0
Java描述设计模式(15):责任链模式

本文源码:GitHub·点这里 || GitEE·点这里 一、生活场景描述 1、请假审批流程 公司常见的请假审批流程:请假天数 当 day<=3 天,项目经理审批当 3<day<=5 天,部门经理审批当 day>5 天...

知了一笑
35分钟前
6
0
总结:数组与链表

1、内存申请:数组在内存上是连续的空间;链表,内存地址上可以是不连续的。 2、查询速度:数组可以随机访问,链表必须顺序访问,即从首个元素开始遍历,逐个查找,所以数组查询很快。 3、写入...

浮躁的码农
43分钟前
6
0
HashMap源码分析

read

V丶zxw
今天
5
0
Python字符串或JSON字符串转字典dict、列表list

有3种方法 1、使用ast模块 >>> import ast>>> s = '["test",1]'>>> ast.literal_eval(s)['test',1]>>> s = '{"test":1}'>>> ast.literal_eval(s){'test': 1} 2、eval函数,这个......

编程老陆
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部