7-39 魔法优惠券 (25 分)

在火星上有个魔法商店，提供魔法优惠券。每个优惠劵上印有一个整数面值K，表示若你在购买某商品时使用这张优惠劵，可以得到K倍该商品价值的回报！该商店还免费赠送一些有价值的商品，但是如果你在领取免费赠品的时候使用面值为正的优惠劵，则必须倒贴给商店K倍该商品价值的金额…… 但是不要紧，还有面值为负的优惠劵可以用！（真是神奇的火星）

例如，给定一组优惠劵，面值分别为1、2、4、-1；对应一组商品，价值为火星币M$7、6、-2、-3，其中负的价值表示该商品是免费赠品。我们可以将优惠劵3用在商品1上，得到M$28的回报；优惠劵2用在商品2上，得到M$12的回报；优惠劵4用在商品4上，得到M$3的回报。但是如果一不小心把优惠劵3用在商品4上，你必须倒贴给商店M$12。同样，当你一不小心把优惠劵4用在商品1上，你必须倒贴给商店M$7。

规定每张优惠券和每件商品都只能最多被使用一次，求你可以得到的最大回报。

输入格式:

输入有两行。第一行首先给出优惠劵的个数N，随后给出N个优惠劵的整数面值。第二行首先给出商品的个数M，随后给出M个商品的整数价值。N和M在[1, 106]之间，所有的数据大小不超过230，数字间以空格分隔。

输出格式:

输出可以得到的最大回报。

输入样例:

1
2

4 1 2 4 -1
4 7 6 -2 -3

输出样例:

1

43

7-38 寻找大富翁 (25 分)

胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。

输入格式:

输入首先给出两个正整数$N$（≤106）和$M$（≤10），其中$N$为总人数，$M$为需要找出的大富翁数；接下来一行给出$N$个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。

输出格式:

在一行内按非递增顺序输出资产排前$M$位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。

输入样例:

1
2

8 3
8 12 7 3 20 9 5 18

输出样例:

1

20 18 12

7-37 模拟EXCEL排序 (25 分)

Excel可以对一组纪录按任意指定列排序。现请编写程序实现类似功能。

输入格式:

输入的第一行包含两个正整数N(≤105) 和C，其中N是纪录的条数，C是指定排序的列号。之后有 N行，每行包含一条学生纪录。每条学生纪录由学号（6位数字，保证没有重复的学号）、姓名（不超过8位且不包含空格的字符串）、成绩（[0, 100]内的整数）组成，相邻属性用1个空格隔开。

输出格式:

在N行中输出按要求排序后的结果，即：当C=1时，按学号递增排序；当C=2时，按姓名的非递减字典序排序；当C=3时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。

输入样例:

1
2
3
4

3 1
000007 James 85
000010 Amy 90
000001 Zoe 60

输出样例:

1
2
3

000001 Zoe 60
000007 James 85
000010 Amy 90

7-35 城市间紧急救援 (25 分)

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式:

输入第一行给出4个正整数$N$、$M$、$S$、$D$，其中$N$（2≤$N$≤500）是城市的个数，顺便假设城市的编号为0 ~ ($N$−1)；$M$是快速道路的条数；$S$是出发地的城市编号；$D$是目的地的城市编号。

第二行给出$N$个正整数，其中第$i$个数是第$i$个城市的救援队的数目，数字间以空格分隔。随后的$M$行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从$S$到$D$的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

1
2
3
4
5
6
7

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

1
2

2 60
0 1 3

7-36 社交网络图中结点的“重要性”计算 (30 分)

在社交网络中，个人或单位（结点）之间通过某些关系（边）联系起来。他们受到这些关系的影响，这种影响可以理解为网络中相互连接的结点之间蔓延的一种相互作用，可以增强也可以减弱。而结点根据其所处的位置不同，其在网络中体现的重要性也不尽相同。

“紧密度中心性”是用来衡量一个结点到达其它结点的“快慢”的指标，即一个有较高中心性的结点比有较低中心性的结点能够更快地（平均意义下）到达网络中的其它结点，因而在该网络的传播过程中有更重要的价值。在有$N$个结点的网络中，结点$v_i$的“紧密度中心性”$C_c(v_i)$数学上定义为$v_i$到其余所有结点$v_j$ ($j ≠ i$) 的最短距离$d$($v_i$,$v_j$)的平均值的倒数：

对于非连通图，所有结点的紧密度中心性都是0。

给定一个无权的无向图以及其中的一组结点，计算这组结点中每个结点的紧密度中心性。

输入格式:

输入第一行给出两个正整数$N$和$M$，其中$N$（≤104）是图中结点个数，顺便假设结点从1到$N$编号；$M$（≤105）是边的条数。随后的$M$行中，每行给出一条边的信息，即该边连接的两个结点编号，中间用空格分隔。最后一行给出需要计算紧密度中心性的这组结点的个数$K$（≤100）以及$K$个结点编号，用空格分隔。

输出格式:

按照Cc(i)=x.xx的格式输出$K$个给定结点的紧密度中心性，每个输出占一行，结果保留到小数点后2位。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

9 14
1 2
1 3
1 4
2 3
3 4
4 5
4 6
5 6
5 7
5 8
6 7
6 8
7 8
7 9
3 3 4 9

输出样例:

1
2
3

Cc(3)=0.47
Cc(4)=0.62
Cc(9)=0.35

7-34 任务调度的合理性 (25 分)

假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。

但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。

输入格式:

输入说明：输入第一行给出子任务数$N$（≤100），子任务按1~$N$编号。随后$N$行，每行给出一个子任务的依赖集合：首先给出依赖集合中的子任务数$K$，随后给出$K$个子任务编号，整数之间都用空格分隔。

输出格式:

如果方案可行，则输出1，否则输出0。

输入样例1:

1
2
3
4
5
6
7
8
9
10
11
12
13

12
0
0
2 1 2
0
1 4
1 5
2 3 6
1 3
2 7 8
1 7
1 10
1 7

输出样例1:

1

1

输入样例2:

1
2
3
4
5
6

5
1 4
2 1 4
2 2 5
1 3
0

输出样例2:

1

0

7-33 地下迷宫探索 (30 分)

地道战是在抗日战争时期，在华北平原上抗日军民利用地道打击日本侵略者的作战方式。地道网是房连房、街连街、村连村的地下工事，如下图所示。

我们在回顾前辈们艰苦卓绝的战争生活的同时，真心钦佩他们的聪明才智。在现在和平发展的年代，对多数人来说，探索地下通道或许只是一种娱乐或者益智的游戏。本实验案例以探索地下通道迷宫作为内容。

假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？

输入格式:

输入第一行给出三个正整数，分别表示地下迷宫的节点数$N$（1<$N$≤1000，表示通道所有交叉点和端点）、边数$M$（≤3000，表示通道数）和探索起始节点编号$S$（节点从1到$N$编号）。随后的$M$行对应$M$条边（通道），每行给出一对正整数，分别是该条边直接连通的两个节点的编号。

输出格式:

若可以点亮所有节点的灯，则输出从$S$开始并以$S$结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的灯，但还是输出点亮部分灯的节点序列，最后输出0，此时表示迷宫不是连通图。

由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。

输入样例1:

1
2
3
4
5
6
7
8
9

6 8 1
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5

输出样例1:

1

1 2 3 4 5 6 5 4 3 2 1

输入样例2:

1
2
3
4
5
6
7

6 6 6
1 2
1 3
2 3
5 4
6 5
6 4

输出样例2:

1

6 4 5 4 6 0

7-32 哥尼斯堡的“七桥问题” (25 分)

哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。

可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。

这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？

输入格式:

输入第一行给出两个正整数，分别是节点数$N$ (1≤$N$≤1000)和边数$M$；随后的$M$行对应$M$条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到$N$编号）。

输出格式:

若欧拉回路存在则输出1，否则输出0。

输入样例1:

1
2
3
4
5
6
7
8
9
10
11

6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6

输出样例1:

1

1

输入样例2:

1
2
3
4
5
6
7
8
9

5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4

输出样例2:

1

0

7-31 笛卡尔树 (25 分)

笛卡尔树是一种特殊的二叉树，其结点包含两个关键字K1和K2。首先笛卡尔树是关于K1的二叉搜索树，即结点左子树的所有K1值都比该结点的K1值小，右子树则大。其次所有结点的K2关键字满足优先队列（不妨设为最小堆）的顺序要求，即该结点的K2值比其子树中所有结点的K2值小。给定一棵二叉树，请判断该树是否笛卡尔树。

输入格式:

输入首先给出正整数N（≤1000），为树中结点的个数。随后N行，每行给出一个结点的信息，包括：结点的K1值、K2值、左孩子结点编号、右孩子结点编号。设结点从0~(N-1)顺序编号。若某结点不存在孩子结点，则该位置给出−1。

输出格式:

输出YES如果该树是一棵笛卡尔树；否则输出NO。

输入样例1:

1
2
3
4
5
6
7

6
8 27 5 1
9 40 -1 -1
10 20 0 3
12 21 -1 4
15 22 -1 -1
5 35 -1 -1

输出样例1:

1

YES

输入样例2:

1
2
3
4
5
6
7

6
8 27 5 1
9 40 -1 -1
10 20 0 3
12 11 -1 4
15 22 -1 -1
50 35 -1 -1

输出样例2:

1

NO

7-30 目录树 (30 分)

在ZIP归档文件中，保留着所有压缩文件和目录的相对路径和名称。当使用WinZIP等GUI软件打开ZIP归档文件时，可以从这些信息中重建目录的树状结构。请编写程序实现目录的树状结构的重建工作。

输入格式:

输入首先给出正整数N（≤104），表示ZIP归档文件中的文件和目录的数量。随后N行，每行有如下格式的文件或目录的相对路径和名称（每行不超过260个字符）：

• 路径和名称中的字符仅包括英文字母（区分大小写）；
• 符号“\”仅作为路径分隔符出现；
• 目录以符号“\”结束；
• 不存在重复的输入项目；
• 整个输入大小不超过2MB。

输出格式:

假设所有的路径都相对于root目录。从root目录开始，在输出时每个目录首先输出自己的名字，然后以字典序输出所有子目录，然后以字典序输出所有文件。注意，在输出时，应根据目录的相对关系使用空格进行缩进，每级目录或文件比上一级多缩进2个空格。

输入样例:

1
2
3
4
5
6
7
8

7
b
c\
ab\cd
a\bc
ab\d
a\d\a
a\d\z\

输出样例:

1
2
3
4
5
6
7
8
9
10
11

root
  a
    d
      z
      a
    bc
  ab
    cd
    d
  c
  b