原題鏈接：POJ1287

解析：這題我用來練習(xí)Prim算法的，算是當(dāng)作一個(gè)模板來看。以下代碼有幾點(diǎn)要說明的：

• 我使用了優(yōu)先隊(duì)列，并沒有使用dist[u]數(shù)組來保存當(dāng)前子樹到 u 的最短距離，這樣省去了找最短路的時(shí)間
• 由于隊(duì)列中存放的最短距離，可能該點(diǎn)已經(jīng)存在子樹中了，所以需要判斷刪除

代碼實(shí)例：

#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; int vis[105];//是否已經(jīng)在子樹中 int graph[105][105]; int p,r; const int inf = 10e7; struct Node{//用來在優(yōu)先隊(duì)列中存放數(shù)據(jù) int val;int id;Node(int val,int id):val(val),id(id){} }; bool operator < (const Node & a,const Node& b){//使用優(yōu)先隊(duì)列要重載小于運(yùn)算符 return a.val > b.val; } int Prim(int cur){//從cur開始進(jìn)行連接結(jié)點(diǎn) int ans = 0;priority_queue<Node> q;memset(vis,0,sizeof vis);for(int u = 1;u < p;u++){vis[cur] = 1;for(int i = 1;i <= p;i++)if(!vis[i] && graph[cur][i] != inf)q.push(Node(graph[cur][i],i)); Node h = q.top();q.pop();while(vis[h.id]){//如果當(dāng)前最小距離的點(diǎn)已經(jīng)全連接在子樹里了，故刪除 h = q.top();q.pop();}cur = h.id;ans += h.val; }return ans; } int main() {scanf("%d",&p);while(p){scanf("%d",&r);int a,b,val;for(int i = 1;i <= p;i++)for(int j = 1;j <= p;j++) graph[i][j] = inf;for(int i = 0;i < r;i++){scanf("%d%d%d",&a,&b,&val);graph[b][a] = graph[a][b] = min(val,graph[a][b]);//倆個(gè)點(diǎn)直接最短距離 }printf("%d\n",Prim(1));scanf("%d",&p);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/long98/p/10352200.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1287 Prim算法模板的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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