第一题： 局域网B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=20010; // 最大节点数
const int M=400010; // 最大边数
int n, m; // n:节点数, m:边数
int e[M], ne[M], h[N], w[M], idx; // 邻接表存储图：e[i]终点, ne[i]下条边索引, h[a]头节点, w[i]边权, idx当前边索引
int dist[N]; // Prim算法中存储节点到生成树的最小距离
bool st[N]; // 标记节点是否已加入生成树
int sum=0; // 存储原始图所有边的权值和
// 添加无向边
void add(int a, int b, int c) {
e[idx] = b; // 记录终点
w[idx] = c; // 记录边权
ne[idx] = h[a]; // 插入链表头部
h[a] = idx++; // 更新头节点索引
}
// Prim算法实现（堆优化）
int prim() {
// 初始化距离数组和标记数组
memset(dist, 0x3f, sizeof(dist)); // 初始化为极大值(0x3f3f3f3f)
memset(st, 0, sizeof(st)); // 初始化为未访问
// 小根堆：按距离排序，存储{distance, node}
priority_queue<PII, vector<PII>, greater<PII>> q;
dist[1] = 0; // 起始节点(1号)距离设为0
q.push({0, 1}); // 初始节点入堆
int res = 0; // 存储最小生成树的总权值
int cnt = 0; // 计数已加入生成树的节点数
while (!q.empty()) {
auto t = q.top(); // 取出距离最小的节点
q.pop();
int ver = t.second; // 当前节点编号
int dis = t.first; // 当前最小距离
if (st[ver]) continue; // 已加入生成树则跳过
st[ver] = true; // 标记为已加入
res += dis; // 累加边权
cnt++; // 节点计数增加
// 遍历当前节点的所有邻接边
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i]; // 邻接节点
// 如果邻接节点未加入生成树且当前边权小于已知最小距离
if (!st[j] && dist[j] > w[i]) {
dist[j] = w[i]; // 更新最小距离
q.push({dist[j], j}); // 入堆（可能重复添加，但堆会筛选最小）
}
}
}
// 如果加入生成树的节点数不足n，说明图不连通
if (cnt != n) return -1;
return res; // 返回最小生成树总权值
}
int main() {
memset(h, -1, sizeof(h)); // 初始化邻接表头节点(-1表示空)
cin >> n >> m;
// 读入m条边
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c); // 添加无向边
add(b, a, c); // 双向添加
sum += c; // 累加原始图的总权值
}
int min_tree = prim(); // 计算最小生成树权值
// 输出原始图总权值 - 最小生成树权值 = 需要删除的边权总和
if(min_tree==-1) cout<<-1<<endl;
else cout<<sum - min_tree<<endl;
return 0;
}
第二题：平面生成树
解法：prim算法+邻接矩阵,这题使用链式向前星存图会爆内存。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
// 常量定义：最大点数
const int N = 5010;
int n; // 点的数量
int dist[N]; // dist[i] 表示点 i 到当前生成树集合的最小边权
bool st[N]; // st[i] 表示点 i 是否已经加入生成树
int dx[N]; // 所有点的 x 坐标
int dy[N]; // 所有点的 y 坐标
int g[N][N]; // 邻接矩阵 g[i][j] 表示 i 到 j 的边权（曼哈顿距离）
// Prim 算法：返回最小生成树的总权值
int prim()
{
// 初始化 dist 数组，所有点到生成树的距离设置为无穷大
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; // 从第 1 个点开始构建生成树，距离设为 0
int ans = 0; // 最小生成树的总边权之和
// 一共加入 n 个点
for(int i = 1; i <= n; ++i)
{
int t = -1; // 当前未加入集合中，距离最小的点
// 找到未加入集合中 dist 最小的点 t
for(int j = 1; j <= n; ++j){
if(st[j]) continue; // 已经在集合中，跳过
if(t == -1 || dist[j] < dist[t]) t = j;
}
// 如果找不到这样的点，说明图不连通
if(dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
st[t] = true; // 将点 t 加入生成树集合
ans += dist[t]; // 累加当前最小边权
// 用 t 点更新其他未加入集合的点到集合的最小边权
for(int j = 1; j <= n; ++j){
if(!st[j] && dist[j] > g[t][j])
dist[j] = g[t][j];
}
}
return ans; // 返回最小生成树的总边权
}
int main()
{
cin >> n; // 输入点数
// 读取每个点的坐标
for(int i = 1; i <= n; ++i)
cin >> dx[i] >> dy[i];
// 初始化邻接矩阵：每两个点之间边权为曼哈顿距离
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(i == j) g[i][j] = 0; // 自己到自己，边权为 0
else g[i][j] = abs(dx[i] - dx[j]) + abs(dy[i] - dy[j]);
// 执行 Prim 算法
int res = prim();
// 判断是否连通并输出结果
if(res == 0x3f3f3f3f) cout << "impossible" << endl;
else cout << res << endl;
return 0;
}
第三题： MST关键边
关键边只会是最小生成树中的某些边，所以每次去除一条最小生成树中的边，再求最小生成树，若值变大或者最小生成树不存在了，则这条边就是关键边。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e5+10; // 定义常量N，表示最大节点数
int n, m; // n-节点数, m-边数
// 定义边的结构体，包含起点a、终点b和权重c
struct edge {
int a, b, c;
};
edge s[200010]; // 存储所有边的数组
int p[200010]; // 并查集父节点数组
bool st[200010]; // 标记边是否被删除
vector<int> q; // 存储最小生成树中的边的下标
// 边排序比较函数：按权重升序排列
bool cmp(edge a, edge b) {
return a.c < b.c;
}
// 并查集查找函数（带路径压缩）
int find(int a) {
if (p[a] != a)
p[a] = find(p[a]); // 递归查找并压缩路径
return p[a]; // 返回根节点
}
// Kruskal算法实现（跳过被标记的边）
int kruskal2() {
for (int i = 1; i <= n; i++)
p[i] = i; // 初始化并查集
int res = 0; // 存储最小生成树的总权重
int cnt = 0; // 计数已选边的数量
// 遍历所有边
for (int i = 1; i <= m; i++) {
if (st[i]) continue; // 跳过被标记（删除）的边
int aa = s[i].a; // 当前边的起点
int bb = s[i].b; // 当前边的终点
int cc = s[i].c; // 当前边的权重
int pa = find(aa); // 查找起点所在集合
int pb = find(bb); // 查找终点所在集合
// 如果不在同一集合，则选择该边
if (pa != pb) {
p[pa] = pb; // 合并集合
res += cc; // 累加权重
cnt++; // 增加已选边计数
}
}
// 判断连通性：最小生成树应有n-1条边
if (cnt < n - 1)
return 0x3f3f3f3f; // 不连通时返回特殊值（无穷大）
else
return res; // 连通时返回总权重
}
// Kruskal算法实现（记录最小生成树的边）
int kruskal1() {
for (int i = 1; i <= n; i++)
p[i] = i; // 初始化并查集
int res = 0; // 存储最小生成树的总权重
int cnt = 0; // 计数已选边的数量
// 遍历所有边
for (int i = 1; i <= m; i++) {
int aa = s[i].a; // 当前边的起点
int bb = s[i].b; // 当前边的终点
int cc = s[i].c; // 当前边的权重
int pa = find(aa); // 查找起点所在集合
int pb = find(bb); // 查找终点所在集合
// 如果不在同一集合，则选择该边
if (pa != pb) {
p[pa] = pb; // 合并集合
res += cc; // 累加权重
cnt++; // 增加已选边计数
q.push_back(i); // 记录该边下标
}
}
// 判断连通性：最小生成树应有n-1条边
if (cnt < n - 1)
return 0x3f3f3f3f; // 不连通时返回特殊值
else
return res; // 连通时返回总权重
}
int main() {
cin >> n >> m; // 输入节点数和边数
// 读入所有边
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
s[i] = {a, b, c}; // 存储边信息
}
sort(s + 1, s + m + 1, cmp); // 按边权重升序排序
int t = kruskal1(); // 计算原图最小生成树权值
int ans = 0; // 关键边数量
// 遍历最小生成树中的每条边
for (int i = 0; i < q.size(); i++) {
st[q[i]] = true; // 标记当前边为删除状态
int k = kruskal2(); // 计算删除该边后的最小生成树权值
// 如果删除后不连通或权值变大，则该边是关键边
if (k > t || k == 0x3f3f3f3f)
ans++;
st[q[i]] = false; // 恢复当前边状态
}
cout << t << endl; // 输出原MST权值
cout << ans << endl; // 输出关键边数量
return 0;
}
第四题：MST边差最小
枚举每条边作为最小边，使用kruskal算法求最小生成树，维护最大边，若能找到最小生成树，更新最小差值。
#include<bits/stdc++.h>
using namespace std;
const int N = 3005; // 最大节点数
const int M = 100010; // 最大边数
const int INF = 0x3f3f3f3f; // 无穷大值
int n, m; // 节点数和边数
int p[N]; // 并查集父节点数组
// 边结构体
struct Edge {
int a, b, c; // 边的两个端点和权重
} edges[M];
// 并查集查找函数（带路径压缩）
int find(int x) {
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
// 边比较函数：按权重升序排序
bool cmp(Edge x, Edge y) {
return x.c < y.c;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edges[i] = {a, b, c};
}
// 按边权重升序排序
sort(edges + 1, edges + m + 1, cmp);
int ans = INF; // 初始化最小差值为无穷大
// 枚举每条边作为最小边
for (int i = 1; i <= m; i++) {
// 初始化并查集
for (int k = 1; k <= n; k++)
p[k] = k;
int cnt = 0; // 当前生成树的边数
int maxEdge = 0; // 当前生成树的最大边权
// 从当前边开始向后扫描
for (int j = i; j <= m; j++) {
// 如果已形成生成树或剩余边数不足，提前终止
if (cnt == n - 1) break;
if (m - j + 1 < n - 1 - cnt) break;
int a = edges[j].a, b = edges[j].b, c = edges[j].c;
int pa = find(a), pb = find(b);
if (pa != pb) {
p[pa] = pb; // 合并两个集合
cnt++; // 增加生成树边数
maxEdge = c; // 更新最大边权
}
}
// 如果成功形成生成树，更新最小差值
if (cnt == n - 1) {
ans = min(ans, maxEdge - edges[i].c);
}
}
printf("%d\n", ans);
return 0;
}
