习题5.1 k 大和(ksum)
【题目描述】
有n 个集合S1, S2 …, Sn，每个集合中各有k 个整数。如果从每个集合Si 中
分别选出一个整数xi，就可以算出它们的和Z=x1+x2+…+xn。
编程求出在所有可能的取法中，前k 大的和。
例如，n=2, k=3，S1={1,4,2}, S2={8,5,6}，则所有可能的和为
S1 选取的元素x1 S2 选取的元素x2 x1+x2
1 8 9
1 5 6
1 6 7
4 8 12
4 5 9
4 6 10
2 8 10
2 5 7
2 6 8
所有和排序的结果为12, 10, 10, 9, 9, 8, 7, 7, 6，因此前3 大的和为12, 10, 10。
【输入】
输入第一行包含两个整数n, k，表示集合的个数和每个集合的元素个数，以
下共n 行，每行包含k 个整数，表示该集合的所有元素。
【输出】
输出只包含k 个整数，表示前k 大的和。这些数应按非增顺序排列。
【样例输入】
2 3
1 4 3
8 5 6
【样例输出】
12 10 10
【限制】
1<=n, k<=5000
每个元素的绝对值不超过105。
习题5.2 移动圆(circle)
【题目描述】
有一个宽度为W 的无限长的通道，内有n 个点状障碍物（可视作半径为0）。
你的任务是把一个尽量大的圆从通道的左侧移到右侧。障碍点可以碰到圆的边
界，但不能进入圆的内部。圆是不可压缩的。圆的边界可以与通道边界相切，但
不可越出。
【输入】
第一行包含两个整数n 和W，表示障碍点个数和通道宽度，以下n 行每行
包括两个整数x, y，表示第i 个障碍点的笛卡尔坐标。通道的边界为y=0 和y=W
【输出】
输出包含一个实数（保留三位小数），表示能从左侧移到右侧的最大圆半径。
【样例输入】
8 5
2 1
1 3
3 2
4 4
5 3
6 4
7 2
7 1
【样例输出】
2.236
【样例图示】
【限制】
1<=n<=1000。所有障碍点的坐标(x, y)满足：0<=x<=105，0<y<W。
习题5.3 绳子(rope)
【题目描述】
我有n 个铁环和m 根等长的绳子，每根绳子的两端分别拴在两个不同的铁
环上。如果我的左手拿着某个铁环L，右手拿着某个铁环R，然后使劲往两边拉
（左手往左，右手往右，始终保持L 和R 的连线水平），那么将会有一些绳子被
绷紧。
我应该选择怎样的L 和R，才能让尽量多的绳子被绷紧呢（如果我的手臂可
以任意伸长）？
假设绳子的粗细可以忽略，被拉伸时不会变形，铁环的厚度和半径也可以忽
略，且不会滑动。
【输入】
输入第一行包括两个整数n, m，以下m 行，每行包括两个整数x, y，表示该
绳子的两端拴在铁环x 和铁环y 上（铁环编号为1, 2, …, n）。每对铁环最多由一
条绳子拴着。
【输出文件】
输出仅包含一个整数，即被绷紧的绳子数目的最大值。
【样例输入】
4 4
1 2
2 3
3 4
4 1
【样例输出】
4
【限制】
左手拿铁环1，右手拿铁环3，则最后绳子1-2, 2-3, 3-4, 4-1 都将被绷紧。
【限制】
1<=n<=100, 1<=m<=1000。
习题5.4 荒岛(island)
【题目描述】
你来到一个荒岛，准备把它建设成为旅游圣地。由于荒岛很大，你决定首先
在岛上修建一些道路，连接岛上的n 处风景宜人的地方（你把它们称为景点，编
号为1, 2, …, n）。
仔细勘测地形之后，你发现其中p 对景点之间已经有道路直接相连了，而另
外q 对景点之间虽然目前还不直接相连，但是在它们之间新建道路相对容易，其
余的n(n-1)/2 - p - q 条道路则因修建成本过高而不予考虑。假设在把这q 条道路
都修通之后，可以保证从任一景点都能直接或间接通往其余景点。但在仔细计算
了这q 条道路的修建时间之后，你希望花尽量少的时间，依然保证这一点。
由于只有你一个人，修路的总时间等于修每条路的时间之和。
【输入】
输入第一行包括三个整数n, p, q，表示景点的个数，已经存在的道路数和目
前还没有，但可以新建的道路数。以下p 行，每行包括两个数x, y，表示已经有
一条道路连接x 和y。以下q 行，每行包括三个数x, y, t，表示x 和y 目前并不
直接相连，但是可以新修一条道路连接x 和y，修路时间为t。
【输出】
输出仅一行，包括一个整数T，表示最短的修路总时间。
【样例输入】
4 1 3
1 2
2 3 3
3 1 2
1 4 5
【样例输出】
7
【限制】
1<=n<=104, n-1<=p+q<=106，所有修路时间均为不超过100 的正整数。
习题5.5 按钮(button)
【题目描述】
一个矩形被划分成N×M 个全等方格，每个格子为黑色或者白色。对应于
每行、每列都有一个按钮，它们的功能如下：
行按钮：把该行所有方格反色（即黑变白，白变黑）。
列按钮：同时按住两个列按钮能交换这两列。
给定初始状态和目标状态，问是否可以从初始状态开始按若干次按钮后到达
目标状态。
【输入】
输入第一行包含一个整数t，表示数据的组数。每组数据的第一行包括两个
数N, M，以下N 行每行有M 个整数，0 表示黑色，1 表示白色，表示初始状态，
以下N 行表示目标状态，格式同上。
【输出】
对每组数据输出Yes 表示可以，No 表示不可以。
【样例输入】
2
3 4
1 0 1 0
0 1 1 0
1 1 1 1
1 0 1 0
0 0 1 1
1 1 1 1
2 3
0 0 0
0 0 0
0 0 0
0 0 1
【样例输出】
Yes
No
【限制】
2<=N, M<=100, 1<=t<=100。