poj----(1251)Jungle Roads(最小生成树)

Jungle Roads

Time Limit: 1000MS

Memory Limit: 10000K

Total Submissions: 19265

Accepted: 8806

Description

The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems. 

Input

The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100. All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above. 

Output

The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit. 

Sample Input

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

Sample Output

216
30

Source

Mid-Central USA 2002

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【面试宝典】c调用c++函数,为什么要加extern c

首先,作为extern是C/C++语言中表明函数和全局变量作用范围(可见性)的关键字,该关键字告诉编译器,其声明的函数和变量可以在本模块或其它模块中使用。 通常...

436140
来自专栏程序员互动联盟

【编程概念】--随机数

在编程的过程中经常遇到需要生成随机数的问题,其实这个就是引用系统自带的随机数函数产生数值来使用。 C/C++怎样产生随机数:这里要用到的是rand()函数, s...

392150
来自专栏程序员互动联盟

【新技术分享】C++17 最新进展

C++标准委员会最近在夏威夷的科纳召开了一次会议,大家可能关心最新的进展,但是按照以往的情况,某些文件需要很久才会公开。会议进行的时候,大家都在忙着修订自己的文...

35560
来自专栏程序员互动联盟

【面试宝典】C++中const关键字的用法

对于刚毕业的应届生来说面试中经常被问到const关键字的用法,小编在这里为大家总结如下: 修饰常量 用const修饰的变量某种意义上就是常量,编译器会对它进行...

27350
来自专栏程序员互动联盟

C语言和C++本质区别在哪?

疑惑一 做网站前端开发需要具备哪些基础知识? 做网站开发分为前端和后台,如果从事前端开发需要学习哪些基础知识呢?现在为大家总结一下。 html: ...

51830
来自专栏程序员互动联盟

【编程牛人】C++之父

本贾尼·斯特劳斯特卢普 1982年,美国AT&T公司贝尔实验室的Bjarne Stroustrup博士在c语言的基础上引入并扩充了面向对象的概念,发明了—种新的...

44560
来自专栏程序员互动联盟

【答疑释惑】C++异常处理是咋回事?

疑惑一 C++的异常处理 一、什么是异常处理 一句话:异常处理就是处理程序中的错误。 二、为什么需要异常处理,以及异常处理的基本思想 C++ 之父Bjarne ...

33950
来自专栏程序员互动联盟

【专业技术】STL hash_map使用(一)

今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。 hash_map类在头文件hash_map中,和所有其...

35180
来自专栏程序员互动联盟

发现要java的那么多,C++不行了嘛?

疑惑一 发现招java的很多,C++不行了嘛? 看看一些公司的招聘简章,大多是招java的居多,传统的编程语言c,c++难道真的不行了,造成这种情况主要是国内互...

37960
来自专栏程序员互动联盟

【专业技术】从4行代码看右值引用

概述   右值引用的概念有些读者可能会感到陌生,其实他和C++98/03中的左值引用有些类似,例如,c++98/03中的左值引用是这样的: int i = 0;...

44670

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励