5-10 公路村村通 (30分)

現(xiàn)有村落間道路的統(tǒng)計數(shù)據(jù)表中，列出了有可能建設(shè)成標(biāo)準(zhǔn)公路的若干條道路的成本，求使每個村落都有公路連通所需要的最低成本。
輸入格式:

輸入數(shù)據(jù)包括城鎮(zhèn)數(shù)目正整數(shù)N（ ≤1000 和候選道路數(shù)目M（ ≤3N ）；隨后的M行對應(yīng)MMM條道路，每行給出3個正整數(shù)，分別是該條道路直接連通的兩個城鎮(zhèn)的編號以及該道路改建的預(yù)算成本。為簡單起見，城鎮(zhèn)從1到N編號。
輸出格式:

輸出村村通需要的最低成本。如果輸入數(shù)據(jù)不足以保證暢通，則輸出?1，表示需要建設(shè)更多公路。
輸入樣例:

6 15 1 2 5 1 3 3 1 4 7 1 5 4 1 6 2 2 3 4 2 4 6 2 5 2 2 6 6 3 4 6 3 5 1 3 6 1 4 5 10 4 6 8 5 6 3

輸出樣例:

12

思路
關(guān)鍵詞：最小生成樹

點擊訪問 PTA-測驗

#include<stdlib.h> #include<stdio.h>/* 評測結(jié)果 時間 結(jié)果 得分 題目 編譯器 用時（ms） 內(nèi)存（MB） 用戶 2016-08-28 07:05 答案正確 30 5-10 gcc 43 5 569985011 測試點結(jié)果 測試點 結(jié)果 得分/滿分 用時（ms） 內(nèi)存（MB） 測試點1 答案正確 15/15 2 1 測試點2 答案正確 2/2 2 1 測試點3 答案正確 2/2 1 1 測試點4 答案正確 5/5 43 5 測試點5 答案正確 6/6 24 5 查看代碼*/ struct data {int VerNode,Coast; }; typedef struct LNode* Vertex; struct LNode {struct data a[1001];int Left,Right; }; void InsertV(Vertex,int ,int,int); int Prim(Vertex ,int ); Vertex CreatV(int); int Comp(const void*a,const void*b) {struct data x=*(struct data *)a;struct data y=*(struct data *)b;return x.Coast - y.Coast ; }int main() {int N,M;scanf("%d%d",&N,&M);Vertex V=CreatV(N+1);int from,to,lenth;for(int i=0; i<M; i++) {scanf("%d%d%d",&from,&to,&lenth);InsertV(V,from,to,lenth);}for(int i=1; i<=N; i++) {qsort(V[i].a,V[i].Right-V[i].Left,sizeof(struct data),Comp); // printf("%d",i); // for(int j=V[i].Left;j<V[i].Right ;j++){ // printf("{-%d=%d}",V[i].a[j].VerNode,V[i].a[j].Coast ); // }printf("\n");}printf("%d",Prim(V,N));return 0; }int Prim(Vertex V,int N) {int right=0,left=0,Node[1001],Coast=0;for(int i=1; i<=N; i++) {if(V[i].Right >V[i].Left) {if(right) {if(V[i].a[0].Coast <V[Node[0]].a[0].Coast) {Node[0]=i;}} else {Node[right++]=i;}}}Coast+=V[Node[0]].a[0].Coast ; Node[right++]=V[Node[0]].a[0].VerNode;V[Node[0]].Left ++; // printf("-%d-",right);while(right<N) {int flag=-1;for(int i=0; i<right; i++) {if(V[Node[i]].Left<V[Node[i]].Right) {if(flag!=-1) {if(V[Node[i]].a[V[Node[i]].Left].Coast <V[Node[flag]].a[V[Node[flag]].Left ].Coast)flag=i;} else {flag=i;}}}if(-1==flag)break;int i;for(i=0;i<right;i++){if(V[Node[flag]].a[V[Node[flag]].Left].VerNode==Node[i])break;}if(i==right){Node[right++]=V[Node[flag]].a[V[Node[flag]].Left].VerNode;Coast+=V[Node[flag]].a[V[Node[flag]].Left].Coast ;}V[Node[flag]].Left++;}for(int i=0;i<right;i++){ // printf("[%d]",Node[i]);} if(right>=N)return Coast;else return -1; }Vertex CreatV(int num) {Vertex V=(Vertex)malloc(sizeof(struct LNode)*num);for(int i=0; i<num; i++) {V[i].Left =0;V[i].Right =0;}return V; } void InsertV(Vertex V,int from,int to,int lenth) {V[from].a[V[from].Right].Coast =lenth;V[from].a[V[from].Right++].VerNode =to;V[to].a[V[to].Right].Coast =lenth;V[to].a[V[to].Right++].VerNode =from; }

總結(jié)

以上是生活随笔為你收集整理的5-10 公路村村通 (30分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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