最小生成树专题1 最小生成树

最小生成树专题1 最小生成树"/>

最小生成树专题1 最小生成树

题目：

样例1：

4 5
0 1 3
0 2 2
0 3 3
2 3 1
1 2 1

 样例2：

3 1
0 1 1

思路：

        Prim 算法和 朴素版的 Dijkstra 有点类似，也叫做 朴素版Prim算法，但也还是有点区别。

Dijkstra 中，只要起点到目的点的最短距离。

最小生成树，表示   不定某个起点和终点，要求遍历完所有点的 最短距离。

所以，朴素版的 Prim 和 朴素版的 Dijkstra 很相似。

区别在于更新 dist 的时候，Dijkstra 更新的是距离，Prim 更新的是 集合之间的最短边。

即

for(int j = 0;j < n;++j)
{dist[j] = min(dist[j],g[t][j]);
}

最小生成树中，是 找 集合到集合之间的  最小边，  Dijkstra最短距离是 节点之间的最小距离。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define INF 0x3f3f3f3f
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 500 + 10;int n,k;int g[N][N];	// 存储结点之间的最短边
bool st[N];	// 标记是否遍历过该点
int dist[N];	// 存储集合之间的最短边inline int Prim()
{// 初始化集合之间的最短边方案为无穷memset(dist,INF,sizeof dist);dist[0] = 0;	// 初始化检查起始点最短边方案为 0int ans = 0;	// 存储最小生成树的最短边for(int i = 0;i < n;++i){int t = -1;	// 探头 t 探索每个结点，哪个是最短边for(int j = 0;j < n;++j){// 如果符合 最短边结点，且为遍历过该结点 那么更新 tif(!st[j] && (t == -1 || dist[j] < dist[t]))t = j;}// 如果存在孤立点 那么肯定无法遍历完所有点，没有最小生成树返回 -1if(i && dist[t] >= INF) return -1;	st[t] = true;	// 标记好已经遍历了 该 t 结点if(i) ans += dist[t];	// 如果已经开始走动了，那么开始存储集合之间的最短边for(int j = 0;j < n;++j) dist[j] = min(dist[j],g[t][j]);	// 更新所有最短边，即 t 点到 j 点之间的最短边}if(ans >= INF) return -1;	// 如果存在孤立点，返回 -1return ans;	// 返回最小生成树最短边
}inline void solve()
{// 初始化集合之间的边长为无穷memset(g,INF,sizeof g);cin >> n >> k;while(k--){int a,b,c;cin >> a >> b >> c;// 存储结点之间最短边g[a][b] = g[b][a] = min(g[a][b],c);}cout << Prim() << endl;
}int main()
{
//	freopen("a.txt", "r", stdin);IOS;int _t = 1;
//	cin >> _t;while (_t--){solve();}return 0;
}

最后提交：