圖結(jié)構(gòu)練習(xí)——最小生成樹

Time Limit:?1000MS?Memory Limit:?65536KB Submit?Statistic?Discuss

Problem Description

?有n個(gè)城市，其中有些城市之間可以修建公路，修建不同的公路費(fèi)用是不同的。現(xiàn)在我們想知道，最少花多少錢修公路可以將所有的城市連在一起，使在任意一城市出發(fā)，可以到達(dá)其他任意的城市。 ?

Input

?輸入包含多組數(shù)據(jù)，格式如下。 第一行包括兩個(gè)整數(shù)n m，代表城市個(gè)數(shù)和可以修建的公路個(gè)數(shù)。(n <= 100， m <=10000) 剩下m行每行3個(gè)正整數(shù)a b c，代表城市a 和城市b之間可以修建一條公路，代價(jià)為c。 ?

Output

?每組輸出占一行，僅輸出最小花費(fèi)。

Example Input

3 2 1 2 1 1 3 1 1 0

Example Output

2 0

Hint

?

Author

#include<iostream> #include <cstring> #define Minimum 0x3f3f3f3f using namespace std; int Map[1010][1010];//用二維數(shù)組來(lái)表示圖的邊的關(guān)系 int visit[1010];//頂點(diǎn)標(biāo)記數(shù)組，值為1表示訪問(wèn)過(guò)，為0則沒(méi)有訪問(wèn)過(guò) int lowcost[1010];//存儲(chǔ)每個(gè)頂點(diǎn)與之相連邊的權(quán)值 int n,m; int prim() {int i,j,k;int sum =0,flag=0;int Min;visit[1]=1;for(i=1;i<=n;i++)//權(quán)值初始化{lowcost[i]=Map[i][1];//鄰接矩陣豎著建立}for(i=2;i<=n;i++){Min = Minimum;for(j=1;j<=n;j++)//尋找每個(gè)頂點(diǎn)與之相連的邊的最小權(quán)值{if(!visit[j]&&lowcost[j]<Min){Min = lowcost[j];k=j;}}sum+=Min;visit[k]=1;for(j=1;j<=n;j++)//從新更新權(quán)值{if(!visit[j]&&lowcost[j]>Map[j][k])lowcost[j]=Map[j][k];}}cout<<sum<<endl;return 0; } int main() {int u,v,w;while(cin>>n>>m){memset(Map,Minimum,sizeof(Map));memset(visit,0,sizeof(visit));if(m<n-1)//有n個(gè)點(diǎn)至少有n-1條路，如果少于說(shuō)明不能完全聯(lián)通cout<<0<<endl;else{while(m--){cin>>u>>v>>w;if(Map[u][v]>w)//防止重復(fù)邊的出現(xiàn)，保留權(quán)值小的Map[u][v]=Map[v][u]=w;}prim();}}return 0; }/*************************************************** User name: YT1658506207邵雪源 Result: Accepted Take time: 44ms Take Memory: 2160KB Submit time: 2017-08-11 19:39:58 ****************************************************/

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的SDUT-2144 图结构练习——最小生成树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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