# 计算机23级数据结构上级实验（第8周）
A 快速排序
给定包含n个元素的整型数组a[1],a[2],...,a[n]，利用快速排序算法对其进行递增排序，请输出排序过程，即每次Partition之后的数组。最后输出排序后的数组。每次选择所处理的子数组的第一个元素作为基准元素。
输入格式:
输入为两行，第一行为一个整数n（1<n≤1000），表示数组长度。第二行为n个空格间隔的整数，表示待排序的数组。
输出格式:
输出为若干行，每行依次输出Partition后的整个数组，每个元素后一个空格。最后一行输出排序后的数组。
输入样例:
5
4 5 3 2 1
输出样例:
2 1 3 4 5
1 2 3 4 5
1 2 3 4 5
提示:
就是在每次调用完Partition函数后输出R[1]….R[n]。其余与快速排序一致。
- 模板题，经典快速排序霍尔版本，while里两个循环找到大数和小数交换
- 不同于书本的是最右侧没有极大值保证避免边界判断所以需要在
- while (a[i] <= key && i < j) { i++; }判断i < j
#include<iostream>
#include<vector>
using namespace std;
// 打印数组中的元素
void Print(const vector<int>& nums)
{
// 遍历数组并打印每个元素，元素之间用空格隔开
for (const auto& i : nums)
{
cout << i << " ";
}
}
// 分区函数：对数组进行分区，返回基准元素的最终位置
int Partition(vector<int>& a, int left, int right)
{
int i = left, j = right + 1; // 初始化 i 和 j，i 从左边界开始，j 从右边界开始
int key = a[left]; // 选择数组的第一个元素作为基准
while (i < j)
{
// 向右移动 i，直到找到一个大于基准的元素
i++;
while (a[i] <= key && i < j) { i++; }//注意边界判断i<J
// 向左移动 j，直到找到一个小于基准的元素
j--;
while (a[j] > key) { j--; }
// 如果 i < j，交换 a[i] 和 a[j]
if (i < j)
swap(a[i], a[j]);
}
// 最后将基准元素放到正确的位置
swap(a[j], a[left]);
return j; // 返回基准元素的位置
}
// 快速排序函数：递归地对数组进行排序
void QuickSort(vector<int>& nums, int left, int right)
{
if (left < right) // 如果左边界小于右边界,即区间里还有两个数未排序
{
int key = Partition(nums, left, right); // 获取基准元素的位置
// 打印每次分区后的数组状态
Print(nums);
cout << endl;
// 递归排序基准元素左边的部分
QuickSort(nums, left, key - 1);
// 递归排序基准元素右边的部分
QuickSort(nums, key + 1, right);
}
}
int main()
{
int n;
cin >> n; // 输入数组的大小
vector<int> nums; // 初始化一个空数组
// 读取数组元素
for (int i = 0; i < n; i++)
{
int v;
cin >> v; // 输入每个元素
nums.push_back(v); // 将元素添加到数组中
}
// 调用快速排序函数，对数组进行排序
QuickSort(nums, 0, n - 1);
// 打印排序后的数组
Print(nums);
cout << endl; // 打印换行符
}
B 网络布线
亚洲杯赛期间需要保证运动员公寓网络畅通，以使运动员都能正常上网。
假定公寓楼内有n个房间，编号为0…n−1，每个房间都需要网络连接。房间 i 有网络，当且仅当满足如下2个条件之一：
（1）房间 i 安装了路由器（成本为 r**i>0）
（2）房间 i 和房间 j 有网线连接且房间 j 有网络（在房间 i 和房间 j 之间布置网线的成本为 f**ij>0）
假定你是赛事组委会的网络工程师，请编写程序设计一个网络布线方案（哪些房间安装路由器，哪些房间之间布置网线），使得所有房间都有网络，且总成本最小。
例如下图包含7个房间和10个可能的连接，安装路由器的成本为括号内数字，房间之间布置网线的成本为边的权值。其解决方案为右下图，即在房间1和4安装路由器，并进行图中的网线布置。总成本为120。
输入格式:
输入第一行为两个正整数n和e；n为房间数，不超过600；e为可能的连接数，不超过2×105。接下来一行为n个空格间隔的正整数，第i个整数(i≥0)表示在房间i安装路由器的成本。接下来e行，每行为3个非负整数i、j、f，表示在房间i和房间j之间布置网线的成本为f。
输出格式:
输出为一个整数，表示最优网络布线方案的成本。
输入样例:
7 10
60 10 35 55 40 70 70
0 1 20
0 4 75
0 3 45
1 3 50
1 2 15
2 6 5
5 6 45
4 5 5
3 5 25
3 6 65
输出样例:
120
提示:
可引入一个虚拟顶点，将该顶点与其他所有顶点用边相连，边权等于那些顶点的权值。进而形成一个新图，对新图求最小支撑树。注意本题顶点编号从0开始。
- 有提示后就成为Prim算法求稠密图的最小生成树的总代价
- 需要注意的点是，因为输入多，并且时间限制得很巧，不优化输入输出就会超时
- 所以需要优化输入输出，分离cin和scanf的缓冲区，或者直接使用scanf
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
// 图的邻接矩阵表示
vector<vector<int>> graph;
// 创建图，包括添加虚拟顶点和边
void CreateGraph() {
int n, e;
cin >> n >> e;
// n号顶点作为虚拟顶点，初始化图的邻接矩阵，所有权值初始为INT_MAX（表示不连通）
graph.resize(n + 1, vector<int>(n + 1, INT_MAX));
// 输入虚拟顶点n与其他顶点之间的边权值
for (int i = 0; i < n; i++) {
int v;
cin >> v;
graph[n][i] = v; // 虚拟顶点到其他顶点
graph[i][n] = v; // 其他顶点到虚拟顶点
}
// 输入图的边
for (int i = 0; i < e; i++) {
int a, b, w;
cin >> a >> b >> w;
graph[a][b] = w; // 无向边，双向赋值
graph[b][a] = w;
}
}
// 使用Prim算法计算最小生成树的总权值
int Prim() {
int ans = 0; // 记录最小生成树的总权值
// 用于存储与每个顶点的最小连接边权值和对应的顶点
vector<pair<int, int>> close_edge;
vector<bool> vis; // 标记顶点是否已被访问
int num = graph.size(); // 图中顶点的数量
int u = num - 1; // 虚拟顶点的编号
vis.resize(num, false); // 初始化访问标记
close_edge.resize(num);
// 初始化close_edge数组，设置每个顶点与虚拟顶点的边权值
for (int i = 0; i < num; i++) {
if (i != u) {
close_edge[i].first = graph[u][i]; // 初始化为虚拟顶点到其他顶点的边权值
close_edge[i].second = u; // 对应的顶点是虚拟顶点
}
}
vis[u] = true; // 将虚拟顶点标记为已访问
// 找到未访问顶点中与生成树连接权值最小的边
auto Min = [&]() -> int {
int minindex = -1; // 最小权值边的顶点编号
int min = INT_MAX; // 最小权值
for (int i = 0; i < close_edge.size(); i++) {
const auto& vex = close_edge[i];
// 未访问且有更小权值的边
if (!vis[i] && vex.first < min) {
minindex = i;
min = vex.first;
}
}
return minindex; // 返回最小权值顶点编号
};
// 循环选择剩余n个顶点中的n-1个，将其加入生成树
for (int i = 1; i < num; i++) {
int u0 = Min(); // 找到当前未访问顶点中连接权值最小的顶点
ans += close_edge[u0].first; // 将最小权值累加到结果中
vis[u0] = true; // 标记该顶点为已访问
// 更新close_edge数组，检查是否存在更小的连接权值
for (int j = 0; j < close_edge.size(); j++) {
if (graph[u0][j] < close_edge[j].first) {
close_edge[j].first = graph[u0][j]; // 更新为更小的权值
close_edge[j].second = u0; // 更新对应顶点
}
}
}
return ans; // 返回最小生成树的总权值
}
int main() {
// 优化输入输出
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// 创建图并计算最小生成树的总权值
CreateGraph();
cout << Prim() << endl;
return 0;
}
C 最大边
给定一个包含n个顶点的无向正权连通图，顶点编号为1到n。请编写程序计算其最小支撑树中任意两个顶点间路径中，权值最大的边的权值。
输入格式:
第一行为2个正整数n和m，n为图中顶点个数，m为边的条数。接下来m行，每行3个整数a、b、c，表示顶点a和顶点b之间有一条权值为c的边。随后一行为一个正整数T，表示查询数目。接下来T行，每行2个整数a和b，表示查询最小支撑树中顶点a和b间路径中的最大边。n≤2000，m≤30000，1 ≤a,b≤ n且a\=b，c ≤65535，T ≤ 1000 。
输出格式:
对于每个查询输出一行，为1个整数，表示最小支撑树两个顶点间的路径中的最大边的权值。
输入样例:
8 20
2 7 44181
1 2 36877
3 6 2506
2 8 46829
7 1 2843
4 5 40699
1 3 15911
7 6 15553
5 6 22541
8 6 62008
3 4 62009
5 7 53337
5 3 12157
4 6 10112
1 5 22574
3 7 28993
4 7 53536
6 1 951
4 2 31411
7 8 31020
10
7 5
5 4
4 2
7 2
3 4
1 5
1 5
7 3
6 1
4 1
输出样例:
12157
12157
31411
31411
10112
12157
12157
2843
951
10112
- 首次思路利用kruskal算法再利用深度优先找到路径，但是超时
#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;
// 边的结构体，表示图中的一条边
struct edge
{
int u; // 边的起点
int v; // 边的终点
int w; // 边的权重
edge(int _u, int _v, int _w) :u(_u), v(_v), w(_w) { }
};
vector<edge> graph; // 图的所有边
vector<vector<edge>> tree; // 存储生成树的邻接表
vector<int> fa; // 并查集父亲数组，用于判断是否在同一个连通块中
// 比较函数，用于按照边的权重排序
bool cmp(edge A, edge B) { return A.w < B.w; }
// 创建图的函数
void CreatGraph()
{
int n, m;
cin >> n >> m; // 输入节点数和边数
tree.resize(n + 1); // 初始化树的邻接表，大小为n+1
fa.resize(n + 1); // 初始化并查集，大小为n+1
for (int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w; // 输入每条边的信息：起点、终点、权重
graph.push_back(edge(a, b, w)); // 将每条边加入图中
}
sort(graph.begin(), graph.end(), cmp); // 按照权重对边进行排序
}
// 并查集的查找操作，带路径压缩
int findroot(int x)
{
return fa[x] == x ? x : fa[x] = findroot(fa[x]);
}
// 并查集的合并操作
void Merge(int x, int y)
{
x = findroot(x);
y = findroot(y);
fa[x] = y; // 将x的根节点指向y
}
// 创建生成树的函数，利用并查集进行kruskal算法
void CreatTree()
{
// 初始化并查集
for (int i = 0; i < fa.size(); i++)
{
fa[i] = i;
}
int nums = 0; // 记录已加入树中的边数
// 按照权重从小到大遍历所有边
for (int i = 0; i < graph.size(); i++)
{
int u = graph[i].u;
int v = graph[i].v;
int x = findroot(u); // 查找u的根
int y = findroot(v); // 查找v的根
if (x != y) // 如果u和v不在同一个连通块中
{
tree[u].push_back(edge(u, v, graph[i].w)); // 将这条边加入生成树
tree[v].push_back(edge(v, u, graph[i].w)); // 生成树是无向图，所以要加反向边
Merge(x, y); // 合并u和v的连通块
nums++; // 增加已加入树中的边数
}
if (nums == fa.size() - 2) // 如果已经加入了n-1条边，生成树完成
{
return;
}
}
}
// 记录答案，存储最小路径的最大边权
int ans = INT_MIN;
vector<bool> vis; // 记录节点是否被访问
// 深度优先搜索，查找a到b的路径
void dfs(int a, int b, vector<int> path)
{
vis[a] = true; // 标记当前节点已访问
for (int i = 0; i < tree[a].size(); i++)
{
vector<int> temp = path; // 复制当前路径
temp.push_back(tree[a][i].w); // 将当前边的权重加入路径
if (tree[a][i].v == b) // 如果找到终点b
{
for (int j = 0; j < temp.size(); j++)
ans = max(ans, temp[j]); // 更新路径中最大的边权
break;
}
else if (!vis[tree[a][i].v]) // 如果终点还未访问
{
dfs(tree[a][i].v, b, temp); // 递归搜索
}
}
}
int main()
{
CreatGraph(); // 创建图
CreatTree(); // 创建生成树
int t;
cin >> t; // 输入查询次数
for (int i = 0; i < t; i++)
{
int a, b;
cin >> a >> b; // 输入每次查询的起点a和终点b
ans = INT_MIN; // 初始化答案
vis.assign(fa.size(), false); // 初始化访问标记数组
vector<int> path; // 存储当前路径
dfs(a, b, path); // 深度优先搜索找到a到b的路径
cout << ans << endl; // 输出查询结果
}
system("Pause"); // 暂停程序，等待用户输入
}
- 紧接着认为是找路径时耗时太多，所以采用每次dfs为尽量多的一对点找到最大边,类似贪心
- 却发现依旧超时
#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;
// 边的结构体，表示图中的一条边
struct edge
{
int u; // 边的起点
int v; // 边的终点
int w; // 边的权重
edge(int _u, int _v, int _w) :u(_u), v(_v), w(_w) { }
};
vector<edge> graph; // 存储图的所有边
vector<vector<edge>> tree; // 存储生成树的邻接表
vector<int> fa; // 并查集的父节点数组，用于判断连通性
// 比较函数，用于按照边的权重从小到大排序
bool cmp(edge A, edge B) { return A.w < B.w; }
// 创建图的函数
void CreatGraph()
{
int n, m;
cin >> n >> m; // 输入节点数和边数
tree.resize(n + 1); // 初始化树的邻接表，大小为n+1
fa.resize(n + 1); // 初始化并查集父节点数组
for (int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w; // 输入每条边的起点、终点和权重
graph.push_back(edge(a, b, w)); // 将每条边加入图中
}
sort(graph.begin(), graph.end(), cmp); // 按照权重对边进行排序
}
// 并查集查找操作，带路径压缩
int findroot(int x)
{
return fa[x] == x ? x : fa[x] = findroot(fa[x]);
}
// 并查集合并操作，将两个连通块合并
void Merge(int x, int y)
{
x = findroot(x);
y = findroot(y);
fa[x] = y; // 将x的根节点指向y
}
// 使用Kruskal算法构建最小生成树
void CreatTree()
{
// 初始化并查集
for (int i = 0; i < fa.size(); i++)
{
fa[i] = i;
}
int nums = 0; // 记录已加入树中的边数
// 按照权重从小到大遍历所有边
for (int i = 0; i < graph.size(); i++)
{
int u = graph[i].u;
int v = graph[i].v;
int x = findroot(u); // 查找u的根
int y = findroot(v); // 查找v的根
if (x != y) // 如果u和v不在同一个连通块中
{
tree[u].push_back(edge(u, v, graph[i].w)); // 将这条边加入生成树
tree[v].push_back(edge(v, u, graph[i].w)); // 生成树是无向图，要加反向边
Merge(x, y); // 合并u和v的连通块
nums++; // 增加已加入树中的边数
}
if (nums == fa.size() - 2) // 如果已加入n-1条边，生成树完成
{
return;
}
}
}
// DFS搜索函数，查找从a到b的路径
int ans = INT_MIN;
vector<bool> vis; // 记录节点是否已访问
// dfs遍历寻找路径上的最大边
void dfs(int a, int b, vector<int> path)
{
vis[a] = true; // 标记当前节点已访问
for (int i = 0; i < tree[a].size(); i++)
{
vector<int> temp = path; // 复制当前路径
temp.push_back(tree[a][i].w); // 将当前边的权重加入路径
if (tree[a][i].v == b) // 如果找到终点b
{
for (int j = 0; j < temp.size(); j++)
ans = max(ans, temp[j]); // 更新路径中最大的边权
}
else if (!vis[tree[a][i].v]) // 如果终点还未访问
{
dfs(tree[a][i].v, b, temp); // 递归搜索
}
}
}
// 存储路径信息的二维数组，用来存储每一对节点之间的最大边权
vector<vector<int>> maxedge;
// 更新路径上经过的每一条边的最大权重
void updata(int v, const vector<pair<int, int>>& path)
{
int temp = INT_MIN;
// 从路径末尾开始，更新路径上每条边的最大边权
for (int i = path.size() - 1; i >= 0; i--)
{
temp = max(temp, path[i].second); // 更新最大边权
maxedge[path[i].first][v] = max(maxedge[path[i].first][v], temp); // 更新最大边权
}
}
// 新的DFS搜索函数，更新最大边权
void new_dfs(int a, vector<pair<int, int>> path)
{
vis[a] = true; // 标记当前节点已访问
updata(a, path); // 更新当前路径上的边的最大边权
for (int i = 0; i < tree[a].size(); i++)
{
int v = tree[a][i].v;
auto temp = path;
temp.push_back({a, tree[a][i].w}); // 将当前边加入路径
if (!vis[v]) new_dfs(v, temp); // 如果未访问过，继续DFS搜索
}
}
// 初始化函数
void Init()
{
// 初始化maxedge为最小值
maxedge.resize(fa.size(), vector<int>(fa.size(), INT_MIN));
vis.resize(fa.size(), false);
// 初始化相邻节点之间的最大边权，即相连边的边权
for (int i = 0; i < tree.size(); i++)
{
for (int j = 0; j < tree[i].size(); j++)
{
int u = tree[i][j].u;
int v = tree[i][j].v;
int w = tree[i][j].w;
maxedge[u][v] = w; // 记录相邻点的边权
}
}
}
int main()
{
CreatGraph(); // 创建图
CreatTree(); // 创建最小生成树
Init(); // 初始化maxedge数组
int t;
cin >> t; // 输入查询次数
for (int i = 0; i < t; i++)
{
int a, b;
cin >> a >> b; // 输入查询的起点a和终点b
// 比较a到b和b到a的最大边权
maxedge[a][b] = max(maxedge[a][b], maxedge[b][a]);
// 如果a到b已经有路径，直接输出最大边权
if (maxedge[a][b] != INT_MIN)
{
cout << maxedge[a][b] << endl;
}
else
{
// 如果没有直接路径，执行DFS查找路径并更新最大边权
vis.assign(fa.size(), false); // 重置访问标记
vector<pair<int, int>> path; // 存储路径
new_dfs(a, path); // 执行DFS搜索
maxedge[a][b] = max(maxedge[a][b], maxedge[b][a]); // 比较两种路径的最大边权
cout << maxedge[a][b] << endl; // 输出最大边权
}
}
system("Pause"); // 暂停程序，等待用户输入
}
- 然后认为是稠密图应该用邻接矩阵存储图，并且用Prim求出最小生成树
- 但依旧失败
#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;
// 边的结构体，表示图中的一条边
struct edge
{
int v; // 边的目标节点
int w; // 边的权重
edge(int _v, int _w) : v(_v), w(_w) { }
};
vector<vector<int>> graph; // 存储图的邻接矩阵，表示节点之间的权重
vector<vector<edge>> tree; // 存储最小生成树的邻接表
vector<bool> vis; // 记录节点是否已访问
// 创建图的邻接矩阵
void CreatGraph()
{
int n, m;
cin >> n >> m; // 输入图的节点数n和边数m
graph.resize(n + 1, vector<int>(n + 1, INT_MAX)); // 初始化邻接矩阵为最大整数值，表示没有边
tree.resize(n + 1); // 初始化树的邻接表
// 输入每条边的起点、终点和权重，填充邻接矩阵
for (int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w;
graph[a][b] = w; // 更新邻接矩阵
graph[b][a] = w; // 因为是无向图，需要更新反向边
}
}
// 使用Prim算法生成最小生成树
void CreatTree()
{
int u = 1; // 从节点1开始
int vexnum = tree.size(); // 获取节点数
// 存储每个节点的最小边的权重，以及该边的另一端节点
std::vector<std::pair<int, int>> close_edge(vexnum, { INT_MAX, u });
std::vector<bool> vis(vexnum, false); // 标记节点是否已访问
vis[u] = true; // 标记起始节点1为已访问
// 初始化与节点u相邻的边
for (int i = 1; i < graph[u].size(); i++)
{
close_edge[i].first = graph[u][i];
close_edge[i].second = u;
}
// 获取最小权值边的索引
auto Min = [&]()->int {
int minindex = -1;
int min = INT_MAX;
for (int i = 1; i < close_edge.size(); i++)
{
const auto& vex = close_edge[i];
// 找到未访问且权重最小的边
if (!vis[i] && vex.first < min)
{
minindex = i;
min = vex.first;
}
}
return minindex;
};
// 生成n-1条边的最小生成树（n=节点数）
for (int j = 1; j < vexnum - 1; j++)
{
int u0 = Min(); // 找到权重最小的边的起点
int v0 = close_edge[u0].second; // 获取该边的终点
int w0 = close_edge[u0].first; // 获取该边的权重
// 将该边加入生成树
tree[u0].push_back(edge(v0, w0));
tree[v0].push_back(edge(u0, w0)); // 添加无向边
vis[u0] = true; // 标记该节点为已访问
// 更新与u0相邻的节点的最小边
for (int i = 1; i < graph[u0].size(); i++)
{
int temp = graph[u0][i];
if (temp < close_edge[i].first)
{
close_edge[i].first = temp;
close_edge[i].second = u0;
}
}
}
}
// 存储每对节点间的最大边权
vector<vector<int>> maxedge;
// 更新路径上的每一条边的最大权重
void updata(int v, const vector<pair<int, int>>& path)
{
int temp = INT_MIN;
// 从路径的末尾开始更新每个边的最大边权
for (int i = path.size() - 1; i >= 0; i--)
{
temp = max(temp, path[i].second); // 更新路径上的最大边权
maxedge[path[i].first][v] = max(maxedge[path[i].first][v], temp); // 更新最大边权
}
}
// 新的DFS搜索函数，用于更新路径上每条边的最大边权
void new_dfs(int a, vector<pair<int, int>> path)
{
vis[a] = true; // 标记当前节点已访问
updata(a, path); // 更新当前路径上的最大边权
// 遍历与当前节点相邻的未访问节点
for (int i = 0; i < tree[a].size(); i++)
{
int v = tree[a][i].v;
auto temp = path;
temp.push_back({a, tree[a][i].w}); // 将当前边加入路径
if (!vis[v]) new_dfs(v, temp); // 如果未访问，继续DFS搜索
}
}
// 初始化maxedge数组
void Init()
{
// 初始化maxedge为最小值
maxedge.resize(tree.size(), vector<int>(tree.size(), INT_MIN));
vis.resize(tree.size(), false);
// 初始化与每个节点相邻的最大边权
for (int i = 1; i < tree.size(); i++)
{
for (int j = 0; j < tree[i].size(); j++)
{
int u = i;
int v = tree[i][j].v;
maxedge[u][v] = tree[i][j].w; // 记录每条边的权重
}
}
}
int main()
{
// 优化输入输出
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
CreatGraph(); // 创建图
CreatTree(); // 创建最小生成树
Init(); // 初始化maxedge数组
int t;
cin >> t; // 输入查询次数
// 对每个查询进行处理
for (int i = 0; i < t; i++)
{
int a, b;
cin >> a >> b; // 输入查询的起点a和终点b
// 比较a到b和b到a的最大边权
maxedge[a][b] = max(maxedge[a][b], maxedge[b][a]);
// 如果a到b已经有路径，直接输出最大边权
if (maxedge[a][b] != INT_MIN)
{
cout << maxedge[a][b] << endl;
}
else
{
// 如果没有直接路径，执行DFS查找路径并更新最大边权
vis.assign(tree.size(), false); // 重置访问标记
vector<pair<int, int>> path; // 存储路径
new_dfs(a, path); // 执行DFS搜索
maxedge[a][b] = max(maxedge[a][b], maxedge[b][a]); // 比较两条路径的最大边权
cout << maxedge[a][b] << endl; // 输出最大边权
}
}
return 0;
}
- 最后发现查询次数过少，不需要dfs时为其他顶点对找到最大边，只需要朴素的方法找到最大边
#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;
// 边的结构体，表示图中的一条边
struct edge
{
int v; // 目标节点
int w; // 边的权重
edge(int _v, int _w) : v(_v), w(_w) { }
};
vector<vector<int>> graph; // 图的邻接矩阵，存储节点之间的边权
vector<vector<edge>> tree; // 存储最小生成树的邻接表
vector<bool> vis; // 访问标记，记录节点是否被访问过
// 创建图的邻接矩阵
void CreatGraph()
{
int n, m;
cin >> n >> m; // 输入图的节点数n和边数m
graph.resize(n + 1, vector<int>(n + 1, INT_MAX)); // 初始化邻接矩阵为最大整数值，表示没有边
tree.resize(n + 1); // 初始化树的邻接表
// 输入每条边的起点、终点和权重，并填充邻接矩阵
for (int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w;
graph[a][b] = w; // 更新邻接矩阵的正向边
graph[b][a] = w; // 更新邻接矩阵的反向边（因为是无向图）
}
}
// 使用Prim算法生成最小生成树
void CreatTree()
{
int u = 1; // 从节点1开始
int vexnum = tree.size(); // 获取节点数
// first存储最小边的权值，second存储该边的起始节点
std::vector<std::pair<int, int>> close_edge(vexnum, { INT_MAX, u });
std::vector<bool> vis(vexnum, false); // 标记节点是否已访问
vis[u] = true; // 标记起始节点1为已访问
// 初始化与节点u相邻的边
for (int i = 1; i < graph[u].size(); i++)
{
close_edge[i].first = graph[u][i];
close_edge[i].second = u;
}
// 获取最小权值边的索引
auto Min = [&]()->int {
int minindex = -1;
int min = INT_MAX;
for (int i = 1; i < close_edge.size(); i++)
{
const auto& vex = close_edge[i];
// 找到未访问且权重最小的边
if (!vis[i] && vex.first < min)
{
minindex = i;
min = vex.first;
}
}
return minindex;
};
// 生成最小生成树，选择n-1条边（n=节点数）
for (int j = 1; j < vexnum - 1; j++)
{
int u0 = Min(); // 找到权重最小的边的起点
int v0 = close_edge[u0].second; // 获取该边的终点
int w0 = close_edge[u0].first; // 获取该边的权重
// 将该边加入生成树
tree[u0].push_back(edge(v0, w0));
tree[v0].push_back(edge(u0, w0)); // 因为是无向图，加入反向边
vis[u0] = true; // 标记该节点为已访问
// 更新与u0相邻的节点的最小边
for (int i = 1; i < graph[u0].size(); i++)
{
int temp = graph[u0][i];
if (temp < close_edge[i].first)
{
close_edge[i].first = temp;
close_edge[i].second = u0;
}
}
}
}
// 用于存储最大边权的变量
int ans = INT_MIN;
// 深度优先搜索（DFS）查找从节点a到节点b的路径上的最大边权
void dfs(int a, int b, int nowmax)
{
vis[a] = true; // 标记当前节点已访问
// 遍历当前节点a的邻接节点
for (int i = 0; i < tree[a].size(); i++)
{
int temp = max(nowmax, tree[a][i].w); // 当前路径的最大边权
if (tree[a][i].v == b)
{
// 找到目标节点b，更新最大边权
ans = max(ans, temp);
}
else if (!vis[tree[a][i].v])
{
// 如果目标节点没有访问过，继续深度搜索
dfs(tree[a][i].v, b, temp);
}
}
}
int main()
{
// 优化输入输出，提高程序效率
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
CreatGraph(); // 创建图的邻接矩阵
CreatTree(); // 使用Prim算法创建最小生成树
vis.resize(graph.size(), false); // 初始化访问标记
int t;
cin >> t; // 输入查询次数
// 对每个查询进行处理
for (int i = 0; i < t; i++)
{
int a, b;
cin >> a >> b; // 输入起点a和终点b
vis.assign(vis.size(), false); // 重置访问标记
ans = INT_MIN; // 重置答案
dfs(a, b, INT_MIN); // 执行DFS查找最大边权
cout << ans << endl; // 输出结果
}
return 0;
}
- 题解办法：
- 在建立最小支撑树时找到最大边
因为加入树的那条边即其他点到新点的必经之路，每次根据新找到的边更新其他最大边即可
#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;
// 边结构体，表示图中的边：v 表示目标顶点，w 表示边的权重
struct edge {
int v, w;
edge(int _v, int _w) : v(_v), w(_w) { }
};
// 邻接矩阵表示图
vector<vector<int>> graph;
// 记录顶点是否被访问过
vector<bool> vis;
// 最小生成树中任意两点之间路径的最大边权值
vector<vector<int>> maxedge;
// 创建图：读取顶点数、边数，并构建邻接矩阵
void CreatGraph() {
int n, m;
cin >> n >> m; // 输入顶点数 n 和边数 m
graph.resize(n + 1, vector<int>(n + 1, INT_MAX)); // 初始化邻接矩阵，所有边的初始权重设为 INT_MAX (无穷大)
maxedge.resize(n + 1, vector<int>(n + 1, INT_MIN)); // 初始化 maxedge 矩阵，表示最小生成树中任意两点之间的最大边权重
// 读取所有边的信息，并更新邻接矩阵
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w; // 输入边的两个端点和边的权重
graph[a][b] = w;
graph[b][a] = w; // 无向图，边是双向的
}
}
// 使用 Prim 算法生成最小生成树，并计算最小生成树中任意两点间的最大边
void CreatTree() {
int u = 1; // 从顶点 1 开始生成最小生成树
int vexnum = graph.size(); // 获取顶点数
// close_edge[i] 用来存储当前最小边的信息，first 存储最小边的权重，second 存储最小边的另一端点
vector<pair<int, int>> close_edge(vexnum, { INT_MAX, u });
// 标记各顶点是否被访问过
vis.resize(vexnum, false);
close_edge[u].first = 0; // 从 u 顶点开始，初始化 close_edge[u] 的边权为 0
vis[u] = true; // 标记 u 顶点已访问
// 初始化 close_edge 数组，填充与 u 相邻的边的信息
for (int i = 1; i < vexnum; i++) {
if (graph[u][i] != INT_MAX) { // 只更新与 u 相连的边
close_edge[i].first = graph[u][i];
close_edge[i].second = u;
}
}
// 用 lambda 表达式来找到当前权值最小的未访问的顶点
auto Min = [&]() -> int {
int minindex = -1;
int min = INT_MAX;
for (int i = 1; i < vexnum; i++) {
// 找到未访问的顶点，并且该顶点的边权最小
if (!vis[i] && close_edge[i].first < min) {
minindex = i;
min = close_edge[i].first;
}
}
return minindex; // 返回最小边权对应的顶点
};
// 构造最小生成树，选择剩余的 n-1 个顶点，生成 n-1 条边
for (int j = 1; j < vexnum - 1; j++) {
// 获取当前最小权值的边对应的顶点
int u0 = Min();
int v0 = close_edge[u0].second;
int w0 = close_edge[u0].first;
// 将边加入最小生成树，并更新 maxedge
maxedge[v0][u0] = maxedge[u0][v0] = w0;
// 更新与 u0 相邻的顶点的信息，记录路径中的最大边权
for (int i = 1; i < vexnum; i++) {
if (vis[i]) { // 如果顶点 i 已访问，更新 maxedge
maxedge[i][u0] = maxedge[u0][i] = max(w0, maxedge[i][v0]);
}
}
vis[u0] = true; // 标记 u0 顶点为已访问
// 更新与 u0 相邻的所有未访问顶点的 close_edge 信息
for (int i = 1; i < vexnum; i++) {
int temp = graph[u0][i];
if (temp < close_edge[i].first && temp != INT_MAX) { // 更新最小边信息
close_edge[i].first = temp;
close_edge[i].second = u0;
}
}
}
}
// 主函数，处理输入和输出
int main() {
ios::sync_with_stdio(false); // 提高输入输出效率
cin.tie(nullptr); // 解除 cin 和 cout 的同步
CreatGraph(); // 创建图
CreatTree(); // 创建最小生成树
int t;
cin >> t; // 输入查询次数
for (int i = 0; i < t; i++) {
int a, b;
cin >> a >> b; // 输入查询的两个顶点
// 输出最小生成树中 a 到 b 路径中的最大边权
cout << maxedge[a][b] << endl;
}
}
评论区 - 计算机23级数据结构上级实验（第8周）