現(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)單起見，城鎮(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 #include <bits/stdc++.h> using namespace std; int ls[1005][1005]; int main() {int N, M, x, y, w, s = 0;cin >> N >> M;for (int i = 1; i <= N; i++) // 初始化矩陣每個(gè)點(diǎn)為無窮大for (int j = 1; j <= N; j++)ls[i][j] = 999999;int dist[1005] = {999999}; // dist[x] 表示x節(jié)點(diǎn)到已有生成樹的最短距離for (int i = 0; i < M; i++){ // 生成鄰接矩陣cin >> x >> y >> w;ls[x][y] = w;ls[y][x] = w;}for (int i = 1; i <= N; i++) // 記錄每個(gè)點(diǎn)到1的最短距離dist[i] = ls[1][i];dist[1] = 0; // 訪問過的點(diǎn)設(shè)為0while (1){ // Prim算法int v = 0;for (int i = 1; i <= N; i++)if (dist[i] < dist[v] && dist[i]) // 找出所有未訪問過的節(jié)點(diǎn)到已有生成樹的最短距離v = i;if (!v)break; // 如果沒有可以能夠連接的點(diǎn)則退出循環(huán)s += dist[v];dist[v] = 0; // 訪問過的點(diǎn)設(shè)為0for (int i = 1; i <= N; i++) // 更新該節(jié)點(diǎn)的鄰接節(jié)點(diǎn)到已有生成樹的最短距離if (ls[v][i] < dist[i])dist[i] = ls[v][i];}bool flag = true;for (int i = 1; i <= N; i++) // 如果每個(gè)節(jié)點(diǎn)的dist值都為零，則生成樹成功，否則表明有點(diǎn)不連通if (dist[i])flag = false;if (flag)cout << s << endl;elsecout << -1 << endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的7-16 公路村村通的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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