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

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

輸出格式:
輸出村村通需要的最低成本。如果輸入數(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

//prim算法求 7-5 公路村村通 (30 分) #include <stdio.h> #include <string.h> #include <stdbool.h> #define INF 0x3f3f3f3f//極大數(shù) int n; int ch[1001][1001]; //村與村之間的路(鄰接矩陣) int L[1001]; //村與最小生成樹(shù)之間的路 int prim(int x) {bool flag[1001];memset(flag, false, sizeof(flag));L[x] = 0;int cou = 0;for (int i = 0; i < n; i++){int u = -1, min = INF;for (int j = 1; j <= n; j++){if (L[j] < min && flag[j] == false){min = L[j];u = j;}}if (u == -1)return -1;cou += L[u];flag[u] = true;for (int j = 1; j <= n; j++){if (ch[u][j] != INF && flag[j] == false){if (ch[u][j] < L[j]){L[j] = ch[u][j];}}}}return cou; } int main() {memset(ch, INF, sizeof(ch));memset(L, INF, sizeof(L));int m;scanf("%d %d", &n, &m);while (m--){int a, b, c;scanf("%d %d %d", &a, &b, &c);ch[a][b] = c;ch[b][a] = c;}int k = prim(1);printf("%d", k); }

總結(jié)

以上是生活随笔為你收集整理的7-5 公路村村通 (30 分)（C语言实现）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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