Jungle Roads

时间:2021-12-10 21:56:29

Description

Jungle Roads
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 题目大意:把各个岛屿看成一个点,求各个岛屿之间,权值最小的路径。(最小生成树)
对于数据,数据输入的第一行n代表岛屿的个数,当为0是结束程序,
接着n-1行开始时为这岛屿的编号,用大写字母表示,接着是一个整数m,
表示与该岛屿连接岛屿的个数,然后该行输入m对数据,
第二个数字表示要重修两岛屿之间桥所需要的时间,输出数据见样例及原题。 代码如下:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>a
using namespace std;
int p[27];//并查集,用于判断两个点是否直接或间接连通
struct per
{
int u,v,w; }map[80];
bool cmp(per a,per b)
{
return a.w<b.w;
}
int find(int x)
{
return x==p[x]?x:p[x]=find(p[x]);
} int main()
{
int n;
while (scanf("%d",&n),n)
{
int i,j;
for(i=0;i<27;i++)
p[i]=i;
int k=0;
for(i=0;i<n-1;i++)//构造边的信息
{
char str;
int m;
cin>>str>>m;
for(j=0;j<m;j++,k++)
{
char str2;
int t;
cin>>str2>>t;
map[k].u=(str-'A');
map[k].v=(str2-'A');
map[k].w=t;
}
} sort(map,map+k,cmp);//将边从小到大排序
int ans=0;//结果
for(i=0;i<k;i++)
{
int x=find(map[i].u);
int y=find(map[i].v);
if(x!=y)
{//如果两点不在同一连通分量里,则将两点连接,并存储该边 ans+=map[i].w;
p[x]=y;
}
}
printf("%d\n",ans);
}
return 0;
}

  

Jungle Roads的更多相关文章

  1. poj 1251 Jungle Roads &lpar;最小生成树&rpar;

    poj   1251  Jungle Roads  (最小生成树) Link: http://poj.org/problem?id=1251 Jungle Roads Time Limit: 1000 ...

  2. Jungle Roads&lbrack;HDU1301&rsqb;

    Jungle Roads Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Tota ...

  3. POJ 1251 &Tab;Jungle Roads (prim)

    D - Jungle Roads Time Limit:1000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64u Su ...

  4. POJ 1251 &amp&semi;&amp&semi; HDU 1301&Tab; Jungle Roads (最小生成树)

    Jungle Roads 题目链接: http://acm.hust.edu.cn/vjudge/contest/124434#problem/A http://acm.hust.edu.cn/vju ...

  5. POJ1251 Jungle Roads 【最小生成树Prim】

    Jungle Roads Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 19536   Accepted: 8970 Des ...

  6. HDU-1301 Jungle Roads(最小生成树&lbrack;Prim&rsqb;)

    Jungle Roads Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other) Total ...

  7. Jungle Roads(最小生成树)

    Jungle Roads Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total ...

  8. POJ 1251 Jungle Roads(最小生成树)

    题意  有n个村子  输入n  然后n-1行先输入村子的序号和与该村子相连的村子数t  后面依次输入t组s和tt s为村子序号 tt为与当前村子的距离  求链接全部村子的最短路径 还是裸的最小生成树咯 ...

  9. Jungle Roads&lpar;kruskar&rpar;

    Jungle Roads 题目链接;http://poj.org/problem?id=1251 Time Limit: 1000MS   Memory Limit: 10000K Total Sub ...

  10. (最小生成树)Jungle Roads -- HDU --1301

    链接: http://acm.hdu.edu.cn/showproblem.php?pid=1301 http://acm.hust.edu.cn/vjudge/contest/view.action ...

随机推荐

  1. 如何对sharepoint图片库的文件夹的图片按照时间排序并分页显示

    /// <summary> /// 获取图片库第一层文件夹--根据文件夹名称排序 /// </summary> /// <param name="siteUrl ...

  2. C&num; 获取wave文件信息【转】

    public class WaveHelper { /// <summary> /// 数据流 /// </summary> private Stream m_WaveData ...

  3. jQuery的图像裁剪插件Jcrop

    1.最基本使用方法     html代码部分: <img src="demo_files/flowers.gif" id="demoImage"/> ...

  4. R语言实战读书笔记&lpar;五&rpar;高级数据管理

    5.2.1 数据函数 abs: sqrt: ceiling:求不小于x的最小整数 floor:求不大于x的最大整数 trunc:向0的方向截取x中的整数部分 round:将x舍入为指定位的小数 sig ...

  5. winform代码反编译后图片等资源文件恢复解决方案

    用Reflector工具反编译的winform代码,图片等资源文件不能很好的反编译成功. 这里有一个笨的解决方案.首先我们要了解图片资源当初加入到工程的几种方式,及他们所在的位置. 一般winform ...

  6. byte数组转16进制 输出到文件

    try { File file = new File(Environment.getExternalStorageDirectory(),"shuju2"); if(!file.e ...

  7. 物联网架构成长之路&lpar;16&rpar;-SpringCloud从入门到吹水

    1.前言 Spring Cloud 现在比较流行,版本更新也是蛮快的,网上资料也是很多.很多参考网上资料就可以学到了.这里给个 http://blog.csdn.net/forezp/article/ ...

  8. spring多个AOP执行先后顺序(面试问题:怎么控制多个aop的执行循序)

    转载:spring多个AOP执行先后顺序(面试问题:怎么控制多个aop的执行循序) 众所周知,spring声明式事务是基于AOP实现的,那么,如果我们在同一个方法自定义多个AOP,我们如何指定他们的执 ...

  9. python&sol;numpy&sol;pandas数据操作知识与技巧

    pandas针对dataframe各种操作技巧集合: filtering: 一般地,使用df.column > xx将会产生一个只有boolean值的series,以该series作为dataf ...

  10. java从远程服务器获取PDF文件并后台打印(使用pdfFox)

    一.java原生方式打印PDF文件 正反面都打印,还未研究出只打印单面的方法,待解决 public static void printFile(String path) throws Exceptio ...