數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)之圖論六：村村通公路

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

Problem Description

當(dāng)前農(nóng)村公路建設(shè)正如火如荼的展開，某鄉(xiāng)鎮(zhèn)政府決定實(shí)現(xiàn)村村通公路，工程師現(xiàn)有各個(gè)村落之間的原始道路統(tǒng)計(jì)數(shù)據(jù)表，表中列出了各村之間可以建設(shè)公路的若干條道路的成本，你的任務(wù)是根據(jù)給出的數(shù)據(jù)表，求使得每個(gè)村都有公路連通所需要的最低成本。

Input

連續(xù)多組數(shù)據(jù)輸入，每組數(shù)據(jù)包括村落數(shù)目N(N <= 1000)和可供選擇的道路數(shù)目M(M <= 3000)，隨后M行對(duì)應(yīng)M條道路，每行給出3個(gè)正整數(shù)，分別是該條道路直接連通的兩個(gè)村莊的編號(hào)和修建該道路的預(yù)算成本，村莊從1～N編號(hào)。?

Output

輸出使每個(gè)村莊都有公路連通所需要的最低成本，如果輸入數(shù)據(jù)不能使所有村莊暢通，則輸出-1，表示有些村莊之間沒有路連通。?

Example Input

5 8 1 2 12 1 3 9 1 4 11 1 5 3 2 3 6 2 4 9 3 4 4 4 5 6

Example Output

19

Hint

Author

#include<iostream> #include <cstring> #define Minimum 0x3f3f3f3f//無窮大 using namespace std; int Map[1010][1010];//用二維數(shù)組來表示圖的邊的關(guān)系 int visit[1010];//頂點(diǎn)標(biāo)記數(shù)組，值為1表示訪問過，為0則沒有訪問過 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;}}if(Min==Minimum)//如果某個(gè)頂點(diǎn)與之相連的邊找不到最小權(quán)值，則表示道路不通{flag = 1;break;}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];}}if(!flag)cout<<sum<<endl;elsecout<<-1<<endl; } int main() {int u,v,w;while(cin>>n>>m){memset(Map,Minimum,sizeof(Map));//memset函數(shù)里面只能賦值為 0 -1（源于對(duì)補(bǔ)碼的機(jī)制）memset(visit,0,sizeof(visit));while(m--){cin>>u>>v>>w;Map[u][v]=Map[v][u]=w;}prim();}return 0; }/*************************************************** User name: YT1658506207邵雪源 Result: Accepted Take time: 0ms Take Memory: 2160KB Submit time: 2017-08-11 19:17:20 ****************************************************/

總結(jié)

以上是生活随笔為你收集整理的SDUT-3362 数据结构实验之图论六：村村通公路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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