先說思路：
看題，使所以點互通，可以看出這使一個求最小生成樹的問題。
兩種方法：
方法一：Kruskal算法：加邊。
方法二：Prim算法：加點。
【下面代碼有兩種，任選其一即可】

現有村落間道路的統計數據表中，列出了有可能建設成標準公路的若干條道路的成本，求使每個村落都有公路連通所需要的最低成本。

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

輸出格式:
輸出村村通需要的最低成本。如果輸入數據不足以保證暢通，則輸出?1，表示需要建設更多公路。

輸入樣例:

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 /*方法一：Kruskal算法*/ /* #include<stdio.h> #include<stdlib.h> #define MAXV 1010 #define MAXE 3030 #define INF 99999 typedef struct Enode{int v1;//頂點int v2;//鄰接點int weight;//權值 }ENode; ENode E[MAXE]; int vset[MAXV+1];//每個頂點的leader/祖先 void sort(ENode E[],int e)//冒泡排序：把e條邊按權值從小到大排序 {int i,j;ENode t;for(i=1;i<e;i++){for(j=0;j<e-i;j++){if(E[j+1].weight<E[j].weight){t=E[j+1];E[j+1]=E[j];E[j]=t;}}} }void Kruskal(ENode E[],int n,int e) {int p1,p2,leader1,leader2;int count,sum=0;//邊數、權值和int i,j;//核心算法for(i=1;i<n+1;i++)vset[i]=i;//初始化：祖先是它自己count=0;j=0;while(j<e){p1=E[j].v1;p2=E[j].v2;//取每條邊對應的兩個頂點leader1=vset[p1];leader2=vset[p2];//取其祖先if(leader1!=leader2){sum +=E[j].weight;count++;if(count>=n-1)break;//最小生成樹：n個頂點，n-1條邊for(i=1;i<=n;i++){if(vset[i]==leader2)vset[i]=leader1;}}j++;}//輸出if(count==n-1)printf("%d\n",sum);else printf("-1\n"); }int main() {int n,e;int i;scanf("%d %d",&n,&e);for(i=0;i<e;i++){scanf("%d %d %d\n",&E[i].v1,&E[i].v2,&E[i].weight);}sort(E,e);Kruskal(E,n,e);return 0; }*//*方法二：Prim算法*/ #include<stdio.h> #include<stdlib.h> #define MAXV 1010 #define INF 9999typedef struct Gnode{int V[MAXV];//頂點集int E[MAXV][MAXV];//邊集int n,e;//頂點數、邊數 }GNode;GNode *CreateGraph() {GNode *G;G=(GNode*)malloc(sizeof(GNode));if(G==NULL)return NULL;int i,j,num1,num2,cost;scanf("%d %d",&(G->n),&(G->e));for(i=1;i<=G->n;i++)G->V[i]=i;//頂點集初始化for(i=1;i<=G->n;i++){//邊集初始化for(j=1;j<=G->n;j++){G->E[i][j]=INF;}}for(i=1;i<=G->e;i++){scanf("%d %d %d",&num1,&num2,&cost);G->E[num1][num2]=cost;G->E[num2][num1]=cost;}return G; } void Prim(GNode *G) {int lowcost[MAXV];int count=0,min,minId,sum=0;int i,j;for(j=1;j<=G->n;j++){lowcost[j]=G->E[1][j];}count++;lowcost[1]=0;while(count<G->n){min=INF;minId=1;for(i=1;i<=G->n;i++){if(lowcost[i]<min && lowcost[i]!=0){min=lowcost[i];minId=i;}}count++;lowcost[minId]=0;sum +=min;for(i=1;i<=G->n;i++){if(lowcost[i]!=0&& G->E[minId][i]<lowcost[i]){lowcost[i]=G->E[minId][i];}}}if(sum>INF)printf("-1");else printf("%d",sum); } int main() {GNode *G;G=CreateGraph();Prim(G);return 0; }

總結

以上是生活随笔為你收集整理的7-1 公路村村通 (30 分)（C语言版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。