題目描述

如題，給出一個無向圖，求出最小生成樹，如果該圖不連通，則輸出orz

輸入輸出格式

輸入格式：

?

第一行包含兩個整數(shù)N、M，表示該圖共有N個結(jié)點和M條無向邊。（N<=5000，M<=200000）

接下來M行每行包含三個整數(shù)Xi、Yi、Zi，表示有一條長度為Zi的無向邊連接結(jié)點Xi、Yi

?

輸出格式：

?

輸出包含一個數(shù)，即最小生成樹的各邊的長度之和；如果該圖不連通則輸出orz

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3 輸出樣例#1：?復(fù)制 7

說明

時空限制：1000ms,128M

數(shù)據(jù)規(guī)模：

對于20%的數(shù)據(jù)：N<=5，M<=20

對于40%的數(shù)據(jù)：N<=50，M<=2500

對于70%的數(shù)據(jù)：N<=500，M<=10000

對于100%的數(shù)據(jù)：N<=5000，M<=200000

?

#include <bits/stdc++.h> #define MAXV 5005 #define INF 0x3fffffff using namespace std; struct Node {int v ,w;Node(int _v ,int _w) : v(_v) ,w(_w) {} }; vector<Node> G[MAXV]; int n ,m ,u ,v ,w; int d[MAXV]; bool vis[MAXV]; int prim(); int main() {scanf("%d%d" ,&n ,&m);for(int i=1 ;i<=m ;i++) {scanf("%d%d%d" ,&u ,&v ,&w);G[u].push_back(Node(v ,w));G[v].push_back(Node(u ,w));}int Ans=prim();if(Ans==-1) printf("orz");else printf("%d" ,Ans);return 0; } int prim() {fill(d ,d+MAXV ,INF);d[1]=0;int ans=0;for(int i=1 ;i<=n ;i++) {int u=-1 ,minn=INF;for(int j=1 ;j<=n ;j++)if(!vis[j] && d[j]<minn) {u=j;minn=d[j];}if(u==-1) return -1;vis[u]=true;ans+=d[u];for(int j=0 ;j<G[u].size() ;j++) {int v=G[u][j].v;if(!vis[v] && G[u][j].w<d[v])d[v]=G[u][j].w;}}return ans; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Roni-i/p/8674899.html

總結(jié)

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

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