HNUCM-2022年秋季学期《算法分析与设计》练习14

目录

问题 A: 最小生成树（Prim）

问题 B: 牛妹的蛋糕

问题 C: 尼科彻斯定理

问题 D: 最小生成树（Kruskal）

问题 E: 单源最短路径问题

问题 F: 搭建电路

问题 G: 丛林小道

问题 H: 低碳出行

---

问题 A: 最小生成树（Prim）

题目描述

使用Prim算法求图的最小生成树(MST)

输入

每组数据分为两个部分，第一部分为图的点数n，和边数m,
第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。

输出

最小生成树，输出时按照边的两个端点的升序输出。（先看左端点，再看右端点，端点不换位置）

思路：按Prime算法思路来就行，不过这里题解使用的是Kruskal算法，结果按题意注意排序。

while True:
    try:
        n, m = map(int, input().split())
        maze = [list(map(int, input().split())) for _ in range(m)]
        _, cnt, visited, res = maze.sort(key=lambda x: x[2]), 1, [], []
        a, b, c = maze.pop(0)
        visited.extend([a, b]), res.append([a, b, c])
        while cnt < n - 1:
            for i in range(len(maze)):
                a, b, c = maze[i]
                if (a not in visited or b not in visited) and (a in visited or b in visited):
                    visited.append(a) if a not in visited else visited.append(b)
                    _, _, cnt = res.append([a, b, c]), maze.pop(i), cnt + 1
                    break
        res.sort()
        for a, b, c in res:
            print(a, b, c)
    except:
        break

问题 B: 牛妹的蛋糕

题目描述

众所周知，牛妹非常喜欢吃蛋糕。

第一天牛妹吃掉蛋糕总数三分之一多一个，第二天又将剩下的蛋糕吃掉三分之一多一个，以后每天吃掉前一天剩下的三分之一多一个，到第n天准备吃的时候只剩下一个蛋糕。

牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？

输入

输入n，0

输出

输出第一天蛋糕的数量。

思路：按题目意思不难知道，前一天 = （今天 + 1）* 3 // 2

while True:
    try:
        n, m = int(input()), 1
        for _ in range(1, n):
            m = (m + 1) * 3 // 2
        print(m)
    except:
        break

问题 C: 尼科彻斯定理

题目描述

验证尼科彻斯定理，即：任何一个整数m的立方都可以写成m个连续奇数之和。

例如：

1^3=1

2^3=3+5

3^3=7+9+11

4^3=13+15+17+19

输入

多组输入，输入一个整数。

输出

输出分解后的字符串。

思路：不难发现中位数是m的平方，根据偶数、奇数稍微处理一下就行。

while True:
    try:
        m, res = int(input()), []
        t = m ** 2
        if m % 2 == 1:
            _, a, b = res.append(t), t - 2, t + 2
        else:
            a, b = t - 1, t + 1
        while len(res) < m:
            _, a, b = res.extend([a, b]), a - 2, b + 2
        res.sort()
        for i in range(m):
            print(f"+{res[i]}", end='') if i != 0 else print(res[i], end='')
        print()
    except:
        break

问题 D: 最小生成树（Kruskal）

题目描述

编程实现Kruskal算法，求图的最小生成树(MST)的权重。

输入

每组数据分为两个部分，第一部分为图的点数n，和边数m, 
第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。 

输出

最小生成树的权重。

思路：按算法的思路实现即可。

while True:
    try:
        n, m = map(int, input().split())
        maze = [list(map(int, input().split())) for _ in range(m)]
        _, cnt, visited, res = maze.sort(key=lambda x: x[2]), 1, [], 0
        a, b, c = maze.pop(0)
        _, res = visited.extend([a, b]), res + c
        while cnt < n - 1:
            for i in range(len(maze)):
                a, b, c = maze[i]
                if (a not in visited or b not in visited) and (a in visited or b in visited):
                    visited.append(a) if a not in visited else visited.append(b)
                    res, _, cnt = res + c, maze.pop(i), cnt + 1
                    break
        print(res)
    except:
        break

问题 E: 单源最短路径问题

题目描述

编程实现Dijkstra算法，求一个有向加权图中，从源点出发到其他各个顶点的最短路径。

输入

第1行第1个值表示顶点个数，第2个值表示边个数；第2行开始为边（两个顶点，边的起点和终点）及权重。

输出

顶点0到每一个顶点的最短路径长度。

思路：按算法的思路实现即可。

def get():
    x, y = float('inf'), -1
    for k in range(n):
        if nums[k] < x and k not in s:
            x, y = nums[k], k
    return y, x
 
 
def update(x: int):
    for k in range(n):
        if k not in s:
            nums[k] = min(nums[x] + maze[x][k], nums[k])
 
 
while True:
    try:
        n, m = map(int, input().split())
        maze, nums, s = [[float('inf')] * n for _ in range(n)], [0] + [float('inf')] * (n - 1), [0]
        for i in range(m):
            a, b, c = map(int, input().split())
            maze[a][b] = c
        for i in range(1, n):
            nums[i] = maze[0][i]
        while len(s) < n:
            index, edg = get()
            nums[index], _ = edg, s.append(index)
            update(index)
        for i in range(n):
            print(nums[i], end='') if i == 0 else print('', nums[i], end='')
        print()
    except:
        break

问题 F: 搭建电路

题目描述

明明迷上了一个搭建电路的游戏。
在游戏中，每次在两个电子元件之间增加一条有效电路（两个元件之间先前没有电路相连）都将获得相应的积分奖励。
已知电子元件数量n和部分电子元件之间的奖励积分值。如何构建一个有效电路将所有元件全部连接起来，并且可以得到最多的积分奖励。

输入

每组输入数据包含m+1行。
第1行输入两个正整数n和m，其中n表示电子元件数量（n<=100），m表示提供了m对电子元件之间的奖励积分值（m<=1000）。两个正整数之间用空格隔开。
第2行到第m+1行对应m对电子元件及其对应的奖励积分值，每一行包含三个正整数，第1个和第2个整数表示电子元件编号（从1开始），第3个整数表示两个元件之间搭建电路的奖励积分num(num<1e9)。整数之间用空格隔开。

输出

每组输出占1行，输出一个正整数，即最多可以得到的积分奖励值。如果没有办法把所有元件全部连接起来，则输出“No solution.”。

思路：最小生成树的变种——最大生成树，排序倒序一下即可，稍微注意判断一下不能连起来的情况，这里用一个flag记录。

while True:
    try:
        n, m = map(int, input().split())
        maze = [list(map(int, input().split())) for _ in range(m)]
        _, cnt, visited, res = maze.sort(reverse=True, key=lambda x: x[2]), 1, [], 0
        a, b, c = maze.pop(0)
        _, res, flag = visited.extend([a, b]), res + c, True
        while cnt < n - 1 and flag:
            flag = False
            for i in range(len(maze)):
                a, b, c = maze[i]
                if (a not in visited or b not in visited) and (a in visited or b in visited):
                    visited.append(a) if a not in visited else visited.append(b)
                    res, _, cnt, flag = res + c, maze.pop(i), cnt + 1, True
                    break
        print(res) if flag else print("No solution.")
    except:
        break

问题 G: 丛林小道

题目描述

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.

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.

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.

思路：就是输入稍微变了一下的最小生成树题目，输入稍微处理一下，如何就可以套用最小生成树的模板。

def get_input():
    ss = []
    for _ in range(1, n):
        tmp = input().split()
        s, m = tmp.pop(0), int(tmp.pop(0))
        for _ in range(m):
            v, cc = tmp.pop(0), int(tmp.pop(0))
            ss.append([s, v, cc])
    return ss
 
 
while True:
    try:
        n = int(input())
        if n == 0:
            break
        maze = get_input()
        _, cnt, visited, res = maze.sort(key=lambda x: x[2]), 1, [], 0
        a, b, c = maze.pop(0)
        _, res = visited.extend([a, b]), res + c
        while cnt < n - 1:
            for i in range(len(maze)):
                a, b, c = maze[i]
                if (a not in visited or b not in visited) and (a in visited or b in visited):
                    visited.append(a) if a not in visited else visited.append(b)
                    res, _, cnt = res + c, maze.pop(i), cnt + 1
                    break
        print(res)
    except:
        break

问题 H: 低碳出行

题目描述

为了做一项关于“爱护环境，从小做起”的公益调查，新司机小明决定开老爸的车从家中前往X市第一小学。从小明家到X市第一小学的交通网络图一共有n个顶点（包括起点小明家和终点X市第一小学）和m条无向边。每条边都有一个碳排放量和一个行驶时间（单位：分钟）。
现在需要你编写一个程序帮助小明实现低碳出行，即寻找一条碳排放量最少的路径，一条路径的碳排放量等于该路径上所有边的碳排放量之和。如果存在两条碳排放量相同的路径，则找出总的行驶时间最少的路径，并输出该路径的总碳排放量和总的时间（分钟）。

输入

单组输入。
在每组输入中，第1行包含两个正整数n和m，分别表示顶点数和边数（n<=1000且m<=1000）。其中，第1号顶点为起点（小明家），第n号顶点为终点（X市第一小学）。两个正整数之间用空格隔开。
第2行到第m+1行表示m条边的信息，每一行包含四个正整数。第1个正整数和第2个正整数表示一条边所对应的两个顶点的编号，第3个正整数表示该边对应的碳排放量，第4个正整数表示该边所对应的行驶时间（单位：分钟）。四个正整数两两之间用空格隔开。

输出

对于每组输入，输出碳排放量最少的路径的总碳排放量和总时间（分钟），如果存在两条碳排放量相同的路径，则输出总的行驶时间最少的路径的总碳排放量和总时间。

思路：归根结底也是单源最短路径问题，注意题目没有说是有向图，所以是无向图，感谢某位李姓大佬的思路点拨！

def dijkstra(s: int, t: int):
    visited, co, ti = [False] * (n + 1), [0] * (n + 1), [0] * (n + 1)
    for i in range(1, n + 1):
        co[i], ti[i] = co2[s][i], tim[s][i]
    co[s], ti[s], visited[s] = 0, 0, True
    for i in range(n - 1):
        index, min_co2, min_time = 0, float('inf'), float('inf')
        for j in range(1, n + 1):
            if not visited[j] and (co[j] < min_co2 or (co[j] == min_co2 and ti[j] < min_time)):
                min_co2, min_time, index = co[j], ti[j], j
        visited[index] = True
        for v in range(1, n + 1):
            tmp_co2, tmp_time = co[index] + co2[index][v], ti[index] + tim[index][v]
            if not visited[v] and (tmp_co2 < co[v] or (tmp_co2 == co[v] and tmp_time < ti[v])):
                co[v], ti[v] = tmp_co2, tmp_time
    print(co[t], ti[t])
 
 
n, m = map(int, input().split())
co2, tim = [[float('inf')] * (n + 1) for _ in range(n + 1)], [[float('inf')] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b, c, d = map(int, input().split())
    co2[a][b] = co2[b][a] = min(c, co2[a][b])
    tim[a][b] = tim[b][a] = min(d, tim[a][b])
dijkstra(1, n)