題目詳情：

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

輸入格式:

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

主要思路：

先補一下鄰接表建圖

鄰接表的處理方法：

（1）圖中頂點用一個一維數(shù)組存儲，當然，頂點也可以用單鏈表來存儲，不過，數(shù)組可以較容易的讀取頂點的信息，更加方便。
（2）圖中每個頂點vi的所有鄰接點構(gòu)成一個線性表，由于鄰接點的個數(shù)不定，所以，用單鏈表存儲，無向圖稱為頂點vi的邊表，有向圖則稱為頂點vi作為弧尾的出邊表。

例如，下圖就是一個無向圖的鄰接表的結(jié)構(gòu)：

?從圖中可以看出，頂點表的各個結(jié)點由data和firstedge兩個域表示，

data是數(shù)據(jù)域，存儲頂點的信息，

firstedge是指針域，指向邊表的第一個結(jié)點，即此頂點的第一個鄰接點。

邊表結(jié)點由adjvex和next兩個域組成。

adjvex是鄰接點域，存儲某頂點的鄰接點在頂點表中的下標，（可以通過此下標在一維頂點數(shù)組中查詢到這個頂點的信息）

next則存儲指向邊表中下一個結(jié)點的指針。

數(shù)據(jù)結(jié)構(gòu)一：邊：

typedef struct ENode *PtrToENode;
struct ENode{Vertex V1, V2;      /* 有向邊<V1, V2> */WeightType Weight;  /* 權(quán)重 */
};
typedef PtrToENode Edge;

數(shù)據(jù)結(jié)構(gòu)二：鄰接點

/* 鄰接點的定義 */
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{Vertex AdjV;        /* 鄰接點下標 */WeightType Weight;  /* 邊權(quán)重 */PtrToAdjVNode Next;    /* 指向下一個鄰接點的指針 */
};

?數(shù)據(jù)結(jié)構(gòu)三：頂點表頭節(jié)點

/* 頂點表頭結(jié)點的定義 */
typedef struct Vnode{PtrToAdjVNode FirstEdge;   /* 指向邊表的第一個結(jié)點，即此頂點的第一個鄰接點 */DataType Data;            /* 存頂點的數(shù)據(jù) *//* 注意：很多情況下，頂點無數(shù)據(jù)，此時Data可以不用出現(xiàn) */
} AdjList[MaxVertexNum];    /* AdjList是鄰接表類型 */

數(shù)據(jù)結(jié)構(gòu)四：圖節(jié)點

/* 圖結(jié)點的定義 */
typedef struct GNode *PtrToGNode;
struct GNode{  int Nv;     /* 頂點數(shù) */int Ne;     /* 邊數(shù)   */AdjList G;  /* 鄰接表 */
};
typedef PtrToGNode LGraph; /* 以鄰接表方式存儲的圖類型 */

初始化有頂點沒有邊的空圖：

LGraph CreateGraph( int VertexNum )
{ /* 初始化一個有VertexNum個頂點但沒有邊的圖 */Vertex V;LGraph Graph;Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立圖 */Graph->Nv = VertexNum;Graph->Ne = 0;/* 初始化鄰接表頭指針 *//* 注意：這里默認頂點編號從0開始，到(Graph->Nv - 1) */for (V=0; V<Graph->Nv; V++)Graph->G[V].FirstEdge = NULL;   //將每個頂點的鄰接鏈表的頭結(jié)點指針設(shè)置為 NULL。return Graph; 
}

插入邊（插入的時候是頭插法）

void InsertEdge( LGraph Graph, Edge E )
{    /* 插入邊 <V1, V2> *//* 為V2建立新的鄰接點 */PtrToAdjVNode NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->AdjV = E->V2;NewNode->Weight = E->Weight;/* 將V2插入V1的表頭，插入的邊表示從v1指向v2 */NewNode->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = NewNode;/* 若是無向圖，還要插入邊 <V2, V1> *//* 為V1建立新的鄰接點 */NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->AdjV = E->V1;NewNode->Weight = E->Weight;/* 將V1插入V2的表頭 */NewNode->Next = Graph->G[E->V2].FirstEdge;Graph->G[E->V2].FirstEdge = NewNode;
}

建圖?

LGraph BuildGraph()
{LGraph Graph;Edge E;Vertex V;int Nv, i;scanf("%d", &Nv);   /* 讀入頂點個數(shù) */Graph = CreateGraph(Nv); /* 初始化有Nv個頂點但沒有邊的圖 */ scanf("%d", &(Graph->Ne));   /* 讀入邊數(shù) */if ( Graph->Ne != 0 ) { /* 如果有邊 */ E = (Edge)malloc( sizeof(struct ENode) ); /* 建立邊結(jié)點 */ /* 讀入邊，格式為"起點 終點 權(quán)重"，插入鄰接矩陣 */for (i=0; i<Graph->Ne; i++) {scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); /* 注意：如果權(quán)重不是整型，Weight的讀入格式要改 */InsertEdge( Graph, E );}} /* 如果頂點有數(shù)據(jù)的話，讀入數(shù)據(jù) */for (V=0; V<Graph->Nv; V++) scanf(" %c", &(Graph->G[V].Data));return Graph;
}

然后是Prim算法：

/* 鄰接矩陣存儲 - Prim最小生成樹算法 */Vertex FindMinDist( MGraph Graph, WeightType dist[] )
{ /* 返回未被收錄頂點中dist最小者 */Vertex MinV, V; WeightType MinDist = INFINITY;for (V=0; V<Graph->Nv; V++) {if ( dist[V]!=0 && dist[V]<MinDist) {/* 若V未被收錄，且dist[V]更小 */MinDist = dist[V]; /* 更新最小距離 */MinV = V; /* 更新對應(yīng)頂點 */}}if (MinDist < INFINITY) /* 若找到最小dist */return MinV; /* 返回對應(yīng)的頂點下標 */else return ERROR;  /* 若這樣的頂點不存在，返回-1作為標記 */
}int Prim( MGraph Graph, LGraph MST )
{ /* 將最小生成樹保存為鄰接表存儲的圖MST，返回最小權(quán)重和 */WeightType dist[MaxVertexNum], TotalWeight;Vertex parent[MaxVertexNum], V, W;int VCount;Edge E;/* 初始化。默認初始點下標是0 */for (V=0; V<Graph->Nv; V++) {/* 這里假設(shè)若V到W沒有直接的邊，則Graph->G[V][W]定義為INFINITY */dist[V] = Graph->G[0][V];parent[V] = 0; /* 暫且定義所有頂點的父結(jié)點都是初始點0 */ }TotalWeight = 0; /* 初始化權(quán)重和     */VCount = 0;      /* 初始化收錄的頂點數(shù) *//* 創(chuàng)建包含所有頂點但沒有邊的圖。注意用鄰接表版本 */MST = CreateGraph(Graph->Nv);E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的邊結(jié)點 *//* 將初始點0收錄進MST */dist[0] = 0;VCount ++;parent[0] = -1; /* 當前樹根是0 */while (1) {V = FindMinDist( Graph, dist );/* V = 未被收錄頂點中dist最小者 */if ( V==ERROR ) /* 若這樣的V不存在 */break;   /* 算法結(jié)束 *//* 將V及相應(yīng)的邊<parent[V], V>收錄進MST */E->V1 = parent[V];E->V2 = V;E->Weight = dist[V];InsertEdge( MST, E );TotalWeight += dist[V];dist[V] = 0;VCount++;for( W=0; W<Graph->Nv; W++ ) /* 對圖中的每個頂點W */if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {/* 若W是V的鄰接點并且未被收錄 */if ( Graph->G[V][W] < dist[W] ) {/* 若收錄V使得dist[W]變小 */dist[W] = Graph->G[V][W]; /* 更新dist[W] */parent[W] = V; /* 更新樹 */}}} /* while結(jié)束*/if ( VCount < Graph->Nv ) /* MST中收的頂點不到|V|個 */TotalWeight = ERROR;return TotalWeight;   /* 算法執(zhí)行完畢，返回最小權(quán)重和或錯誤標記 */
}

其實本題可以只用鄰接矩陣構(gòu)建的圖（或鄰接表構(gòu)建的圖)也能解決，因為本題只要求MST的權(quán)值，并沒有考察更多MST的性質(zhì)，不過就當鞏固所學吧?

代碼實現(xiàn)：

#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE_NUMS 1005
#define INFINITY 100000
#define TRUE 1
#define FALSE 0
#define NONE -1
#define ROOT 1
typedef int bool;
/*ListGraph的數(shù)據(jù)結(jié)構(gòu)*/
/*邊*/
typedef struct ENode ENode;
typedef ENode* PToEdgeNode;
struct ENode {int Start, End, Weight;
};
/*鄰接點*/
typedef struct AdjVNode AdjVNode;
typedef AdjVNode* PToAdjVNode;
struct AdjVNode {int VertexIndex, Weight;PToAdjVNode Next;
};
/*頭結(jié)點*/
typedef struct HeadNode HeadNode;
struct HeadNode {int Weight;PToAdjVNode FirstEdge;
};
/*圖節(jié)點*/
typedef struct ListGraphNode ListGraphNode;
typedef ListGraphNode* ListGraph;
struct ListGraphNode {int EdgeNums, VertexNums;HeadNode AdjList[MAX_NODE_NUMS];
};
/*建一個空圖*/
ListGraph CreateEmptyListGraph(int vertexNums) {ListGraph LGraph = (ListGraph)malloc(sizeof(ListGraphNode));LGraph->EdgeNums = 0; LGraph->VertexNums = vertexNums;for(int i = 0; i <= vertexNums; i++) {LGraph->AdjList[i].FirstEdge = NULL;}return LGraph;
}
/*插入邊*/
void InsertEdgeInLGraph(ListGraph LGraph, PToEdgeNode edge) {/*插入<start, end>的邊*/PToAdjVNode newVertex = (PToAdjVNode)malloc(sizeof(AdjVNode));newVertex->VertexIndex = edge->End;newVertex->Weight = edge->Weight;newVertex->Next = LGraph->AdjList[edge->Start].FirstEdge;LGraph->AdjList[edge->Start].FirstEdge = newVertex;/*插入<end,start>的邊，這是因為無向圖，如果是有向圖可以省略*/newVertex = (PToAdjVNode)malloc(sizeof(AdjVNode));newVertex->VertexIndex = edge->Start;newVertex->Weight = edge->Weight;newVertex->Next = LGraph->AdjList[edge->End].FirstEdge;LGraph->AdjList[edge->End].FirstEdge = newVertex;return;
}
ListGraph BuildListGraph(int vertexNums, int edgeNums) {ListGraph LGraph = CreateEmptyListGraph(vertexNums);for(int i = 0; i < edgeNums; i++) {PToEdgeNode newEdge = (PToEdgeNode)malloc(sizeof(ENode));scanf("%d %d %d", &(newEdge->Start), &(newEdge->End), &(newEdge->Weight));InsertEdgeInLGraph(LGraph, newEdge);free(newEdge);}return LGraph;
}/*MatrixGraph的數(shù)據(jù)結(jié)構(gòu)*/
typedef struct MatrixGraphNode MatrixGraphNode;
typedef MatrixGraphNode* MatrixGraph;
struct MatrixGraphNode {int VertexNums, EdgeNums;int Weight[MAX_NODE_NUMS][MAX_NODE_NUMS];
};
MatrixGraph CreateEmptyMatrixGraph(int vertexNums) {MatrixGraph MGraph = (MatrixGraph)malloc(sizeof(MatrixGraphNode));MGraph->VertexNums = vertexNums;MGraph->EdgeNums = 0;for(int i = 0; i <= vertexNums; i++) {for(int j = 0; j <= vertexNums; j++) {MGraph->Weight[i][j] = INFINITY;}}return MGraph;
}
void InsertEdgeInMGraph(int start, int end, int weight, MatrixGraph MGraph) {MGraph->Weight[start][end] = weight;MGraph->Weight[end][start] = weight;return;
}
MatrixGraph BuildMGraph(int vertexNums, int edgeNums) {MatrixGraph MGraph = CreateEmptyMatrixGraph(vertexNums);MGraph->EdgeNums = edgeNums;for(int i = 0; i < edgeNums; i++) {int start, end, weight;scanf("%d %d %d", &start, &end, &weight);InsertEdgeInMGraph(start, end, weight, MGraph);}return MGraph;
}
/*Prim算法*/
/*在剩余節(jié)點中找到與最小生成樹權(quán)值最小的邊*/
int FindMinDis(MatrixGraph MGraph, const int dis[]) {int minV = NONE;int minDist = INFINITY;for(int i = 1; i <= MGraph->VertexNums; i++) {if(dis[i] != FALSE && dis[i] < minDist) { //dist其實兼顧了Dijkstra中vis數(shù)組的作用minDist = dis[i];minV = i;}}return minV;
}
int Prim(MatrixGraph MGraph) {int dis[MAX_NODE_NUMS];     //dis[i]表示節(jié)點i到最小生成樹的距離int parent[MAX_NODE_NUMS];int totalWeight = 0;int Vcount = 0;/*初始化dis和path數(shù)組，默認是從下標1開始，因為頂點從下標1開始*/for(int i = 1; i <= MGraph->VertexNums; i++) {dis[i] = MGraph->Weight[ROOT][i];  //由初始化可以看出，如果ROOT(定這個ROOT的原因是因為最小生成樹只有一個根節(jié)點)~i兩個節(jié)點之間有邊，就初始化為權(quán)值，否則就初始化為INFINITYparent[i] = ROOT;    //假設(shè)所有頂點的上一級頂點都是ROOT}/*開始建立最小生成樹*/ListGraph MST = CreateEmptyListGraph(MGraph->VertexNums);dis[ROOT] = 0;    //將頂點1作為最小生成樹的根節(jié)點Vcount++;parent[ROOT] = NONE;while(TRUE) {int minV = FindMinDis(MGraph, dis);if(minV == NONE) break;/*將minV加入到最小生成樹中*/PToEdgeNode newEdge = (PToEdgeNode)malloc(sizeof(ENode));newEdge->Start = parent[minV];newEdge->End = minV;newEdge->Weight = dis[minV];InsertEdgeInLGraph(MST, newEdge);Vcount++;totalWeight += dis[minV];dis[minV] = FALSE;    //防止重復加入/*更新dis和path數(shù)組*/for(int i = 1; i <= MGraph->VertexNums; i++) {if(dis[i] != FALSE && MGraph->Weight[minV][i] < INFINITY) {   //如果i是之前找到的最小頂點的鄰接點并且沒有收錄if(dis[i] > MGraph->Weight[minV][i]) {  //如果收錄最小的節(jié)點minV后使得節(jié)點i到最小生成樹MST的距離變小dis[i] = MGraph->Weight[minV][i];   parent[i] = minV;}}}free(newEdge);}free(MST);if(Vcount < MGraph->VertexNums) return NONE;return totalWeight;
}
int main() {int vertexNums, edgeNums;scanf("%d %d", &vertexNums, &edgeNums);MatrixGraph MGraph = BuildMGraph(vertexNums, edgeNums);printf("%d", Prim(MGraph));free(MGraph);return 0;
}