发帖
雷达卡
2025年北京大学计算机专业复试上机考试真题
最小生成树问题
题目说明
时间限制：1000 ms
内存限制：256 mb
给定一个包含 n 个顶点的完全图，图中所有边的权重均为 0 或 1，并且恰好有 m 条边的权重为 1。其余边的权重默认为 0。
任务是求出该图的一棵最小生成树（MST），并输出其总边权值之和。仅需返回结果数值即可。
输入格式：
第一行包含两个整数 n 和 m，分别代表节点数量与权重为 1 的边的数量。
其中 m ≤ min{200000, n(n1)/2}。
接下来的 m 行，每行给出两个整数 a[i] 和 b[i]，表示一条连接 a[i] 与 b[i] 的无向边，其权重为 1（满足 1 ≤ a[i] < b[i] ≤ n）。
所有输入的边互不重复。
输出格式：
输出一个整数，表示最小生成树中所有边的权重总和。
样例输入：
6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
样例输出：
2
田忌赛马策略问题
题目描述
时间限制：1000 ms
内存限制：256 mb
源自经典故事“田忌赛马”，现扩展为 N 匹马之间的对抗赛。双方各有 N 匹马，按等级从 1 到 N 分为 N 个级别。比赛进行 N 轮，每轮各派出一匹马对决。
我方只有在派出的马比对方马高出至少 X 个等级（含 X）时，才能赢得该轮比赛。若在整个系列赛中，我方获胜的场次数超过对手，则判定我方获得最终胜利。
已知对方在 N 场比赛中出马的顺序（即每轮使用的马的等级），请计算并列出所有能使我方取得总体胜利的出战方案。
输入格式：
第一行两个整数 N 和 X，其中 N ≤ 9，0 ≤ X < N。
第二行包含 N 个正整数 A(1) 到 A(N)，其中 A(i) 表示对方在第 i 场比赛中所用马的等级（等级越高表示越强）。
输出格式：
按字典序升序输出所有可行的我方获胜方案，每个方案独占一行。
每行包含 N 个正整数，第 i 个数字代表我方在第 i 场比赛中派出马的等级。
样例输入：
3 1
3 2 1
样例输出：
1 3 2
京公网安备 11010802022788号
