題目分析

來源：acwing

分析：

給定一張邊帶權(quán)的無向圖 G=(V,E)，其中 V 表示圖中點的集合，E 表示圖中邊的集合，n=|V|，m=|E|。

由 V 中的全部 n 個頂點和 E 中 n?1 條邊構(gòu)成的無向連通子圖被稱為 G 的一棵生成樹，其中邊的權(quán)值之和最小的生成樹被稱為無向圖 G 的最小生成樹。

樸素prim算法思路：

距離初始化為∞

迭代n次（集合S表示：當(dāng)前連通塊中的所有點）
每次找到集合外距離集合最近的點 t
用t更新其他點到集合的距離
將t加入集合

可以發(fā)現(xiàn)，思路和dijkstra算法很像，dijkstra算法是用t更新其他點到起點的距離，而prim算法是用t更新其他點到集合的距離。

最小生成樹：圖中可能存在重邊和自環(huán)，邊權(quán)可能為負(fù)數(shù)。
ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 510; const int INF = 0x3f3f3f3f; int n, m; int g[N][N]; int dist[N]; bool 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;if(i) res += dist[t];// 注意這里和dijkstra的區(qū)別// prim的距離是：該點和集合中某點的距離，直接就是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(){cin >> n >> m;memset(g, 0x3f, sizeof g);while(m --){int a, b ,c;cin >> 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;}

題目來源

https://www.acwing.com/problem/content/860/

總結(jié)

以上是生活随笔為你收集整理的最小生成树板子-AcWing 858. Prim算法求最小生成树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。