蓝桥杯题库中的算法提升试题

1.算法提高求最大值

时间限制：1.0s 内存限制：256.0MB

问题描述

给n个有序整数对ai bi，你需要选择一些整数对使得所有你选定的数的ai+bi的和最大。并且要求你选定的数对的ai之和非负，bi之和非负。

输入格式

输入的第一行为n，数对的个数

以下n行每行两个整数ai bi

输出格式

输出你选定的数对的ai+bi之和

样例输入

5

-403 -625

-847 901

-624 -708

-293 413

886 709

样例输出

1715

数据规模和约定

1<=n<=100

-1000<=ai,bi<=1000

2.算法提高P1001

时间限制：1.0s 内存限制：256.0MB

当两个比较大的整数相乘时，可能会出现数据溢出的情形。为避免溢出，可以采用字符串的方法来实现两个大数之间的乘法。具体来说，首先以字符串的形式输入两个整数，每个整数的长度不会超过8位，然后把它们相乘的结果存储在另一个字符串当中（长度不会超过16位），最后把这个字符串打印出来。例如，假设用户输入为：62773417和12345678，则输出结果为：774980393241726.

输入：

62773417 12345678

1

输出：

774980393241726

3.算法提高盾神与条状项链

时间限制：1.0s 内存限制：256.0MB

问题描述

有一天，盾神捡到了好多好多五颜六色的珠子！他心想这些珠子这么漂亮，可以做成一条项链然后送给他心仪的女生~于是他用其中一些珠子做成了长度为n的项链。当他准备把项链首尾相接的时候，土方进来了。

“哇这么恶心的项链你也做得出来！！！”

盾神自知审美不是他的长项，于是他很谦虚地请教土方，怎么才能把项链做得漂亮。

“这个嘛~首先你要在这里加上一个这种颜色的珠子，然后在这里去掉这个珠子，然后……，最后你看看是不是漂亮很多咧~”土方一下子说出了m个修改步骤。

盾神觉得这个用人工做太麻烦了，于是交给了你。

输入格式

第一行两个数，分别为n，m。

第二行n个数，表示盾神一开始的项链。第i个数表示第i颗珠子的颜色。

接下来m行，为以下形式之一：

ADD P Q：表示在颜色为P的珠子前面加上一个颜色为Q的珠子。

DEL P：表示把颜色为P的珠子去掉，如果它不在端点处，则需要把它旁边的两颗珠子连起来。例如某时刻项链状态为1 4 5 8，则执行DEL 4会变成1 5 8，执行DEL 1会变成4 5 8。

输入保证在每次操作之前，项链有颜色为P的珠子，且任意时刻珠子颜色互不相同。输出格式

第一行为一个数len，为做完所有操作后，项链的长度。

第二行len个数，表示此时项链的状态。第i个数表示第i颗珠子的颜色。

样例输入

10 5

1 2 3 4 5 6 7 8 9 10

DEL 5

ADD 7 5

DEL 10

ADD 4 20

ADD 20 12

样例输出

11

1 2 3 12 20 4 6 5 7 8 9

2

数据规模和约定

表示颜色的数字不超过10^5的正数，1<=n<=10^4，1<=m<=10^4。

4.算法提高排列数

时间限制：1.0s 内存限制：256.0MB

问题描述

0、1、2三个数字的全排列有六种，按照字母序排列如下：

012、021、102、120、201、210

输入一个数n

求0~9十个数的全排列中的第n个（第1个为0123456789）。

输入格式

一行，包含一个整数n

输出格式

一行，包含一组10个数字的全排列

样例输入

1

样例输出

0123456789

数据规模和约定

0 < n <= 10!

5.算法提高简单加法

时间限制：1.0s 内存限制：256.0MB

问题描述

小于10的自然数中有四个数字能除尽3或5（3，5，6，9），它们的和为23。

请计算所有小于1000的自然数中能除尽3或5的数字的合。然后使用标准输出cout，输出你的结果。

输入格式

无。

输出格式

一行一个整数，表示你的结果。

3

6.算法提高三个整数的排序

时间限制：1.0s 内存限制：256.0MB

问题描述

输入三个数，比较其大小，并从大到小输出。

输入格式

一行三个整数。

输出格式

一行三个整数，从大到小排序。

样例输入

33 88 77

样例输出

88 77 33

7.算法提高身份证号码升级

时间限制：1.0s 内存限制：256.0MB

问题描述

从1999年10月1日开始，公民身份证号码由15位数字增至18位。(18位身份证号码简介)。升级方法为：

1、把15位身份证号码中的年份由2位(7,8位)改为四位。

2、最后添加一位验证码。验证码的计算方案：

将前17 位分别乘以对应系数(7 9 10 5 8 4 2 1 6 3 7 9 10 5 8 4 2) 并相加，然后除以11 取余数，0-10 分别对应1 0 x 9 8 7 6 5 4 3 2。

请编写一个程序，用户输入15位身份证号码，程序生成18位身份证号码。假设所有要升级的身份证的四位年份都是19××年

输入格式

一个15位的数字串，作为身份证号码

输出格式

一个18位的字符串，作为升级后的身份证号码

样例输入

110105*********

样例输出

4

110105************

数据规模和约定

不用判断输入的15位字符串是否合理

8.算法提高快乐司机

时间限制：1.0s 内存限制：256.0MB

问题描述

"嘟嘟嘟嘟嘟嘟

喇叭响

我是汽车小司机

我是小司机

我为祖国运输忙

运输忙"

这是儿歌“快乐的小司机”。话说现在当司机光有红心不行，还要多拉快跑。多拉不是超载，是要让所载货物价值最大，特别是在当前油价日新月异的时候。司机所拉货物为散货，如大米、面粉、沙石、泥土......

现在知道了汽车核载重量为w，可供选择的物品的数量n。每个物品的重量为gi,价值为pi。求汽车可装载的最大价值。（n<10000,w<10000,0

输入格式

输入第一行为由空格分开的两个整数n w

第二行到第n+1行，每行有两个整数，由空格分开，分别表示gi和pi

输出格式

最大价值（保留一位小数）

样例输入

5 36

99 87

68 36

79 43

75 94

7 35

样例输出

71.3

解释：

先装第5号物品，得价值35，占用重量7

再装第4号物品，得价值36.346,占用重量29

最后保留一位小数，得71.3

5

9.算法提高金明的预算方案

时间限制：1.0s 内存限制：256.0MB

问题描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件附件

电脑打印机，扫描仪

书柜图书

书桌台灯，文具

工作椅无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N 元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j_1，j_2，……，j_k，则所求的总和为：

v[j_1]*w[j_1]+v[j_2]*w[j_2]+ …+v[j_k]*w[j_k]。（其中*为乘号）

请你帮助金明设计一个满足要求的购物单。

输入格式

输入文件budget.in 的第1行，为两个正整数，用一个空格隔开：

N m

（其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数

v p q

（其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）

输出格式

6

输出文件budget.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

样例输入

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

样例输出

2200

10.算法提高题目1 最大最小值

时间限制：1.0s 内存限制：1.0GB

问题描述

给定N 个整数，请你找出这N 个数中最大的那个和最小的那个。

输入格式

第一行包含一个正整数N。(1 ≤ N≤ 10000)。

第二行为N个用空格隔开的整数,每个数的绝对值不超过1000000。

输出格式

输出仅一行,包含两个整数x,y，x表示N个数中的最大值，y表示N个数中的最小值。x,y之间用一个空格隔开。

样例输入

4

2 0 1 2

样例输出

2 0。

算法提高新建Microsoft Word文档

时间限制：1.0s 内存限制：256.0MB

问题描述

L正在出题，新建了一个word文档，想不好取什么名字，身旁一人惊问：“你出的题目叫《新建Microsoft Word文档》吗？”，L大喜，一拍桌子，说：“好，就叫这个名字了。”

仔细观察，当你新建一个word文档时，会得到一个名为“新建Microsoft Word 文档.doc”

7

的文件，再新建一个，则名为“新建Microsoft Word 文档(2).doc”，再新建，便是“新建Microsoft Word 文档(3).doc”。不断新建，编号不断递增。倘若你现在新建了三个文档，然后删除了“新建Microsoft Word 文档(2).doc”，再新建就又会得到一个“新建Microsoft Word 文档(2).doc”。

严格说，Windows在每次新建文档时，都会选取一个与已有文件编号不重复的最小正整数作为新文档的编号。

请编程模拟以上过程，支持以下两种操作

New：新建一个word文档，反馈新建的文档的编号

Delete id：删除一个编号为id的word文档，反馈删除是否成功

初始时一个文件都没有，“新建Microsoft Word 文档.doc”的编号算作1。

输入格式

第一行一个正整数n表示操作次数，接下来n行，每行表示一个操作。若该行为”New”，则表示新建，为”Delete id”则表示要删除编号为id的文档，其中id为一个正整数。操作按输入顺序依次进行。

输出格式

对于输入的每一行，输出其反馈结果。对于新建操作，输出新建的文档的编号；对于删除操作，反馈删除是否成功：如果删除的文件存在，则删除成功，输出”Successful”，否则输出”Failed”。

样例输入

12

New

New

New

Delete 2

New

Delete 4

Delete 3

Delete 1

New

New

New

Delete 4

样例输出

1

2

3

Successful

8

2

Failed

Successful

Successful

1

3

4

Successful

数据规模和约定

操作次数（即输入的行数）不超过1481

删除编号的数值不超过2012

11.算法提高上帝造题五分钟

时间限制：1.0s 内存限制：256.0MB

问题描述

第一分钟，上帝说：要有题。于是就有了L，Y，M，C

第二分钟，LYC说：要有向量。于是就有了长度为n写满随机整数的向量

第三分钟，YUHCH说：要有查询。于是就有了Q个查询，查询向量的一段区间内元素的最小值

第四分钟，MZC说：要有限。于是就有了数据范围

第五分钟，CS说：要有做题的。说完众神一哄而散，留你来收拾此题

输入格式

第一行两个正整数n和Q，表示向量长度和查询个数

接下来一行n个整数，依次对应向量中元素：a[0]，a[1]，…，a[n-1]

接下来Q行，每行两个正整数lo，hi，表示查询区间[lo, hi]中的最小值，即

min(a[lo],a[lo+1],…,a[hi])。

输出格式

共Q行，依次对应每个查询的结果，即向量在对应查询区间中的最小值。

样例输入

7 4

1 -1 -4 8 1

2 -7

0 0

1 3

4 5

0 6

样例输出

9

1

-4

1

-7

样例说明

第一个查询[0,0]表示求min{a[0]}=min{1}=1

第二个查询[1,3]表示求min{a[1],a[2],a[3]}=min{-1,-4,8}=-4

第三个查询[4,5]表示求min{a[4],a[5]}=min{1,2}=1

第四个查询[0,6]表示查询整个向量，求min{a[0..6]}=min{1,-1,-4,8,1,2,-7}=-7

数据规模和约定

1<=n<=1984，1<=Q<=1988，向量中随机整数的绝对值不超过1,000

12.算法提高金陵十三钗

时间限制：1.0s 内存限制：256.0MB

金陵十三钗

本题难度：难

本题占分比例：5%

问题描述

在电影《金陵十三钗》中有十二个秦淮河的女人要自我牺牲代替十二个女学生去赴日本人的死亡宴会。为了不让日本人发现，自然需要一番乔装打扮。但由于天生材质的原因，每个人和每个人之间的相似度是不同的。由于我们这是编程题，因此情况就变成了金陵n钗。给出n个女人和n个学生的相似度矩阵，求她们之间的匹配所能获得的最大相似度。

所谓相似度矩阵是一个n*n的二维数组like[i][j]。其中i,j分别为女人的编号和学生的编号，皆从0到n-1编号。like[i][j]是一个0到100的整数值，表示第i个女人和第j个学生的相似度，值越大相似度越大，比如0表示完全不相似，100表示百分之百一样。每个女人都需要找一个自己代替的女学生。

最终要使两边一一配对，形成一个匹配。请编程找到一种匹配方案，使各对女人和女学生之间的相似度之和最大。

输入格式

第一行一个正整数n表示有n个秦淮河女人和n个女学生

接下来n行给出相似度，每行n个0到100的整数，依次对应二维矩阵的n行n列。输出格式

仅一行，一个整数，表示可获得的最大相似度。

样例输入

4

97 91 68 14

8 33 27 92

10

36 32 98 53

73 7 17 82

样例输出

354

数据规模和约定

对于70%的数据，n<=10

对于100%的数据，n<=13

样例说明

最大相似度为91+92+93+73=354

13.算法提高周期字串

时间限制：1.0s 内存限制：256.0MB

问题描述

右右喜欢听故事，但是右右的妈妈总是讲一些“从前有座山，山里有座庙，庙里有个老

和尚给小和尚讲故事，讲的什么呢？从前有座山……”这样循环的故事来搪塞右右。

我们定义，如果一个字符串是以一个或者一个以上的长度为k的重复字符串所连接成的，那么这个字符串就叫做周期为k的串。

例如:

字符串?abcabcabcabc?周期为3，因为它是由4个循环?abc?组成的。它同样是以6为周期（两个重复的?abcabc?）和以12为周期（一个循环?abcabcabcabc?）。

右右现在想给他的朋友大灰狼转述妈妈讲的故事，请帮他写一个程序，可以测定一个字符串的最小周期。

输入格式

一个最大长度为100的无空格的字符串。

输出格式

一个整数，表示输入的字符串的最小周期。

样例输入

HaHaHa

样例输出

2

样例输入

Return0

样例输出

11

7

14.算法提高学霸的迷宫

时间限制：1.0s 内存限制：256.0MB

问题描述

学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。

输入格式

第一行两个整数n，m，为迷宫的长宽。

接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。

输出格式

第一行一个数为需要的最少步数K。

第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。

样例输入

Input Sample 1:

3 3

001

100

110

Input Sample 2:

3 3

000

000

000

样例输出

Output Sample 1:

4

RDRD

12

Output Sample 2:

4

DDRR

数据规模和约定

有20%的数据满足：1<=n,m<=10

有50%的数据满足：1<=n,m<=50

有100%的数据满足：1<=n,m<=500。

15.算法提高01背包

时间限制：1.0s 内存限制：256.0MB

问题描述

给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.

输入格式

输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。

以后N行每行两个数Wi和Vi,表示物品的重量和价值

输出格式

输出1行，包含一个整数，表示最大价值。

样例输入

3 5

2 3

3 5

4 7

样例输出

8

数据规模和约定

1<=N<=200,M<=5000.

16.算法提高扶老奶奶过街

时间限制：1.0s 内存限制：256.0MB

一共有5个红领巾，编号分别为A、B、C、D、E，老奶奶被他们其中一个扶过了马路。

五个红领巾各自说话：

A ：我和E都没有扶老奶奶

13

B ：老奶奶是被C和E其中一个扶过大街的

C ：老奶奶是被我和D其中一个扶过大街的

D ：B和C都没有扶老奶奶过街

E ：我没有扶老奶奶

已知五个红领巾中有且只有２个人说的是真话，请问是谁扶这老奶奶过了街？

若有多个答案，在一行中输出，编号之间用空格隔开。

例如

A B C D E（这显然不是正确答案）

17.算法提高判断名次

时间限制：1.0s 内存限制：256.0MB

问题描述

某场比赛过后，你想要知道A~E五个人的排名是什么，于是要求他们每个人说了一句话。（经典的开头……-_-!）得了第1名的人23，说了假话；得了第5名的人不好意思，也说了假话；为了使求解问题简单，第3名同样说了假话。（奇数名次说假话）

输入格式

共5行，各行依次表示A~E说的话。

每行包含一个形如“A>=3”的名次判断，即一个大写字母+关系运算符+一个数字，不包含空格。

大写字母A~E，关系运算<、<=、=、>=、>、!=，数字1~5。注意：等于是“=”不是“==”！输出格式

可能有多解，请按照字典序输出排名序列，每个解一行

最后一行输出解的数量

样例输入

A=2

D=5

E>3

A>2

B!=1

14

样例输出

ACDEB

AECBD

BADCE

BCADE

BDACE

CEADB

CEBDA

7

18.算法提高日期计算

时间限制：1.0s 内存限制：256.0MB

问题描述

已知2011年11月11日是星期五，问YYYY年MM月DD日是星期几？注意考虑闰年的情况。尤其是逢百年不闰，逢400年闰的情况。

输入格式

输入只有一行

YYYY MM DD

输出格式

输出只有一行

W

数据规模和约定

1599 <= YYYY <= 2999

1 <= MM <= 12

1 <= DD <= 31，且确保测试样例中YYYY年MM月DD日是一个合理日期

1 <= W <= 7，分别代表周一到周日

样例输入

2011 11 11

样例输出

5

19.算法提高概率计算

时间限制：1.0s 内存限制：256.0MB

问题描述

15

生成n个∈[a,b]的随机整数，输出它们的和为x的概率。

输入格式

一行输入四个整数依次为n，a，b，x，用空格分隔。

输出格式

输出一行包含一个小数位和为x的概率，小数点后保留四位小数

样例输入

2 1

3 4

样例输出

0.3333

数据规模和约定

对于50%的数据，n≤5.

对于100%的数据，n≤100,b≤100.

20.算法提高6-17复数四则运算

时间限制：1.0s 内存限制：512.0MB

设计复数库，实现基本的复数加减乘除运算。

输入时只需分别键入实部和虚部，以空格分割，两个复数之间用运算符分隔；输出时按a+bi的格式在屏幕上打印结果。参加样例输入和样例输出。

注意考虑特殊情况，无法计算时输出字符串"error"。

样例输入

2 4 * -

3 2

样例输出

-14-8i

样例输入

3 -2 + -1 3

样例输出

2+1i

21.算法提高c++_ch02_01

时间限制：1.0s 内存限制：512.0MB

编写一个程序，利用强制类型转换打印元音字母大小写10种形式的ASCII码。

输出的顺序为：大写的字母A，E，I，O，U的ASCII码，小写的字母a，e，i，o，u

16

的ASCII码。所有的ASCII码都用十进制表示.输出10行,每行一个ASCII码，最后输出一个空行。

22.算法提高逆序排列

时间限制：1.0s 内存限制：512.0MB

问题描述

编写一个程序，读入一组整数（不超过20个），并把它们保存在一个整型数组中。当用户输入0时，表示输入结束。然后程序将把这个数组中的值按逆序重新存放，并打印出来。例如：假设用户输入了一组数据：7 19 -5 6 2 0，那么程序将会把前五个有效数据保存在一个数组中，即7 19 -5 6 2，然后把这个数组中的值按逆序重新存放，即变成了2 6 -5 19 7，然后把它们打印出来。

输入格式：输入只有一行，由若干个整数组成，中间用空格隔开，最末尾的整数为0。

输出格式：输出也只有一行，即逆序排列后的整数，中间用空格隔开，末尾没有空格。

输入输出样例

样例输入

7 19 -5 6 2 0

样例输出

2 6 -5 19 7

23.算法提高第二大整数

时间限制：1.0s 内存限制：512.0MB

问题描述

编写一个程序，读入一组整数（不超过20个），当用户输入0时，表示输入结束。然后程序将从这组整数中，把第二大的那个整数找出来，并把它打印出来。说明：（1）0表示输入结束，它本身并不计入这组整数中。（2）在这组整数中，既有正数，也可能有负数。（3）这组整数的个数不少于2个。

输入格式：输入只有一行，包括若干个整数，中间用空格隔开，最后一个整数为0。

输出格式：输出第二大的那个整数。

输入输出样例

样例输入

5 8 -12 7 0

样例输出

7

24.算法提高约数个数

17

时间限制：1.0s 内存限制：512.0MB 输入一个正整数N (1

样例输入

12

样例输出

6

样例说明

12的约数包括：1,2,3,4,6,12。共6个

25.算法提高十进制数转八进制数

26.算法提高复数归一化

18

27.算法提高最大乘积

时间限制：1.0s 内存限制：512.0MB

28.算法提高最小方差生成树

时间限制：1.0s 内存限制：256.0MB

问题描述

给定带权无向图，求出一颗方差最小的生成树。

输入格式

输入多组测试数据。第一行为N,M，依次是点数和边数。接下来M行，每行三个整数U,V,W，代表连接U,V的边，和权值W。保证图连通。n=m=0标志着测试文件的结束。输出格式

对于每组数据，输出最小方差，四舍五入到0.01。输出格式按照样例。

样例输入

19

4 5

1 2 1

2 3 2

3 4 2

4 1 1

2 4 3

4 6

1 2 1

2 3 2

3 4 3

4 1 1

2 4 3

1 3 3

0 0

样例输出

Case 1: 0.22

Case 2: 0.00

数据规模与约定

1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。数据不超过5组。

29.算法提高道路和航路

时间限制：1.0s 内存限制：256.0MB

问题描述

农夫约翰正在针对一个新区域的牛奶配送合同进行研究。他打算分发牛奶到T个城镇（标号为1..T），这些城镇通过R条标号为（1..R）的道路和P条标号为（1..P）的航路相连。

每一条公路i或者航路i表示成连接城镇A i（1<=A_i<=T）和B i（1<=B i<=T）代价为C i。每一条公路，C i的范围为0<=C i<=10,000；由于奇怪的运营策略，每一条航路的C i可能为负的，也就是-10,000<=C i<=10,000。

每一条公路都是双向的，正向和反向的花费是一样的，都是非负的。

每一条航路都根据输入的A i和B i进行从A i->B i的单向通行。实际上，如果现在有一条航路是从A i到B i的话，那么意味着肯定没有通行方案从B i回到A i。

农夫约翰想把他那优良的牛奶从配送中心送到各个城镇，当然希望代价越小越好，你可以帮助他嘛？配送中心位于城镇S中（1<=S<=T）。

输入格式

输入的第一行包含四个用空格隔开的整数T，R，P，S。

20

接下来R行，描述公路信息，每行包含三个整数，分别表示A i，B i和C i。

接下来P行，描述航路信息，每行包含三个整数，分别表示A i，B i和C i。

输出格式

输出T行，分别表示从城镇S到每个城市的最小花费，如果到不了的话输出NO PATH。样例输入

6 3 3 4

1 2 5

3 4 5

5 6 10

3 5 -100

4 6 -100

1 3 -10

样例输出

NO PATH

NO PATH

5

-95

-100

数据规模与约定

对于20%的数据，T<=100，R<=500，P<=500；

对于30%的数据，R<=1000，R<=10000，P<=3000；

对于100%的数据，1<=T<=25000，1<=R<=50000，1<=P<=50000。

30.算法提高金属采集

时间限制：1.0s 内存限制：256.0MB

问题描述

人类在火星上发现了一种新的金属！这些金属分布在一些奇怪的地方，不妨叫它节点好了。一些节点之间有道路相连，所有的节点和道路形成了一棵树。一共有n 个节点，这些节点被编号为1~n 。人类将k 个机器人送上了火星，目的是采集这些金属。这些机器人都被送到了一个指定的着落点，S 号节点。每个机器人在着落之后，必须沿着道路行走。当机器人到达一个节点时，它会采集这个节点蕴藏的所有金属矿。当机器人完成自己的任务之后，可以从任意一个节点返回地球。当然，回到地球的机器人就无法再到火星去了。我们已经提前测量出了每条道路的信息，包括它的两个端点x 和y，以及通过这条道路需要花费的能量w 。我们想花费尽量少的能量采集所有节点的金属，这个任务就交给你了。

21

本文来源：https://www.bwwdw.com/article/706l.html