蓝桥杯 C++ 算法训练 安慰奶牛

蓝桥杯 C++ 算法训练 安慰奶牛

来源: | 浏览: 4054 | 评论: 2发表时间: 2014-01-17 15:37:17

Farmer John变得非常懒,他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场,牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路,但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。



问题描述

第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej),而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心,因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过),你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜,直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候,你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务。假设Farmer John采纳了你的建议,请计算出使所有奶牛都被安慰的最少时间。


输入格式

第1行包含两个整数N和P。

接下来N行,每行包含一个整数Ci。

接下来P行,每行包含三个整数Sj, Ej和Lj。


输出格式

输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。


样例输入

5 7

10

10

20

6

30

1 2 5

2 3 5

2 4 12

3 4 17

2 5 15

3 5 6

4 5 12


(蓝桥杯网站上的题目测试用例中少了最后一组数据)


样例输出

176


数据规模与约定

5 <= N <= 10000,N-1 <= P <= 100000,0 <= Lj <= 1000,1 <= Ci <= 1,000。


解题思路

由于在行走过程中,两边都要花时间,而且路上要来回花2倍的时间,那么判断一条路径的权就可以用路权*2+两端点权,然后使用普里姆或者克鲁斯卡尔算法等求出最小生成树就行了. 我使用了克鲁斯卡尔算法,在查找集合时使用并查集.


同时,在蓝桥的评测系统上这个代码只有两组数据AC,可能是蓝桥的数据有问题吧 = = .
再附一组测试数据:4 4 10 5 5 5 1 2 20 2 3 5 3 4 15 2 4 10 结果110




相关文章
  • 声明: 评论属于其发表者所有,不代表本站的观点和立场.
  • 个人博客回复该留言时间: 2014-01-17 16:56:02

    博主应该还是一个学生吧!

  • 石博文回复该留言时间: 2014-01-18 05:49:04

    嗯:)

已有 2 位网友发表了一针见血的评论,你还等什么?
  • 昵称: *
  • 邮箱:
  • 网址:
  • 记住我的信息
  • Color
  • Red
  • Blue
  • Code
  • bash
  • cpp
  • css
  • java
  • js
  • perl
  • php
  • python
  • ruby
  • sql
  • xml