题目描述
稠密图 - 朴素版Prim O(n^2)
和 Dijkstra 算法 非常相似。
具体步骤:
dist[i] 初始化成 正无穷
for(i = 0; i < n ; i ++) 这里是迭代n次(Dijkstra是已经选中第一个点了,再选其他点,所以是 n - 1 次迭代)
找到不在集合(当前生成块-连通块)中最近的点 t;
用 t 更新其他点到集合的距离;(Dijkstra 是用 t 更新其他点到集合的距离);
把 t 加到集合中去; st[t] = true;
当前集合指:当前已经在连通块当中的所有点;
其他点到集合的距离:看一下其他点有没有一条边能连向集合内部;
某一个点到集合的距离指:这个点到集合内部的所有边当中 长度最小的 边;
样例
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N= 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int prime()
{
memset(dist, 0x3f, sizeof dist);
// res 存的是 最小生成树里面所有边的长度之和
int res = 0;
for(int i = 0; i < n; i ++)
{
// 首先找到当前不在集合中的距离最近的点, t = -1 表示没找到
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;
// 先更新 res 再 更新其他点, 如果有自环的话,在后面 可能 会把 dist[t] 更新了
// 只要不是第一个点,dist[t] 表示的是 当前这个点 和现在这个已经连好的某一条边的长度
if(i) res += dist[t];
// 注意这里和 Dijkstra 的区别,Dijkstra写的是 dist[t] = min(dist[j], dist[t] + g[t][j])
for(int j = 1; j <= n; j ++) dist[j] = min(dist[j], g[t][j]);
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 = prime();
if(t == INF) puts("impossible");
else printf("%d\n", t);
return 0;
}