题目描述
给定一个 $n$ 个点 $m$ 条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible
。
给定一张边带权的无向图 $G=(V,E)$,其中 $V$ 表示图中点的集合,$E$ 表示图中边的集合,$n=|V|$,$m=|E|$。
由 $V$ 中的全部 $n$ 个顶点和 $E$ 中 $n−1$ 条边构成的无向连通子图被称为 $G$ 的一棵生成树,其中边的权值之和最小的生成树被称为无向图 $G$ 的最小生成树。
输入格式
第一行包含两个整数 $n$ 和 $m$。
接下来 $m$ 行,每行包含三个整数 $u,v,w$,表示点 $u$ 和点 $v$ 之间存在一条权值为 $w$ 的边。
输出格式
共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible
。
数据范围
$1≤n≤500,$
$1≤m≤10^5,$
图中涉及边的边权的绝对值均不超过 $10000$。
样例
输入样例:
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例:
6
算法
Prim
时间复杂度
$O(n^2)$
参考文献
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n,m;
// 稠密图
// 使用邻接矩阵存储
int g[N][N];
// dist存储 点到集合的距离
int dist[N];
// st集合存储当前在连通块中的点(为true,则说明在连通块中)
int st[N];
// 求最小生成树
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0; // 最小生成树中所有边的权重之和
for(int i=0; i<n; i++)
{
int t = -1;
// 找到集合外距离集合最近的点
for (int j=1; j<=n; j++)
if (!st[j] && (t==-1 || dist[t] > dist[j]))
t=j;
// 说明无法构造最小生成树
if (i && dist[t] == INF) return INF;
// 当i不为0的时候, 才累加(也就是说 当选取第一个点的时候不累加)
if (i) res += dist[t]; //先累加,再更新(因为如果存在自环的话会更小)
// 用t更新其他点到集合的距离
for (int j=1; j<=n; j++)
dist[j] = min(dist[j], g[t][j]);
// 将t点添加到集合中
st[t] = true;
}
return res;
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g); // 初始化图,假设每个点之间的距离都是无穷大
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if (t == INF) puts("impossible");
else cout<<t<<endl;
return 0;
}