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

輸入格式:

輸入數據包括城鎮數目正整數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

代碼實現：

#include<stdio.h>
#include<stdlib.h>
typedef struct ArcNode* Arc;
struct ArcNode
{int adjvex1;int adjvex2;int weight;
};int st[1001]={0};
struct ArcNode Edge[3001];void createNode(int v1,int v2,int cost,int);
void Traverse(int);
void build(int,int);
int w=0;
int flag=0;
//flag用于判斷是否是選擇的第一條邊
int main()
{int N,M;scanf("%d%d",&N,&M);for(int i=0;i<M;i++){int v1,v2,cost;scanf("%d%d%d",&v1,&v2,&cost);createNode(v1,v2,cost,i);}if(M<N-1){printf("-1\n");}else{build(N,M);}return 0;
}
void createNode(int v1,int v2,int cost,int i)
{Edge[i].adjvex1=v1;Edge[i].adjvex2=v2;Edge[i].weight=cost;return;
}
void Traverse(int M)
{//Prim算法int min=1000;int pos=-1;for(int i=0;i<M;i++){int v1=Edge[i].adjvex1;int v2=Edge[i].adjvex2;if(flag==0||(st[v1]^st[v2])){if(Edge[i].weight<min){min=Edge[i].weight;pos=i;}}}w+=Edge[pos].weight;int v1=Edge[pos].adjvex1;int v2=Edge[pos].adjvex2;st[v1]=1;st[v2]=1;flag=1;return;
}
void build(int N,int M)
{for(int i=1;i<N;i++){Traverse(M);}for(int i=1;i<=N;i++){if(st[i]==0){printf("-1\n");return;}}printf("%d\n",w);return;
}

本題使用普利姆算法相對于克魯斯卡爾算法更好實現