時間限制：1 秒

內存限制：32 兆

特殊判題：否

提交：3140

解決：1338

題目描述：

省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可）。現得到城鎮道路統計表，表中列出了任意兩城鎮間修建道路的費用，以及該道路是否已經修通的狀態。現請你編寫程序，計算出全省暢通需要的最低成本。

輸入：

測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數目N ( 1< N < 100 )；隨后的 N(N-1)/2 行對應村莊間道路的成本及修建狀態，每行給4個正整數，分別是兩個村莊的編號（從1編號到N），此兩村莊間道路的成本，以及修建狀態：1表示已建，0表示未建。

??? 當N為0時輸入結束。

輸出：

每個測試用例的輸出占一行，輸出全省暢通需要的最低成本。

樣例輸入：

3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0

樣例輸出：

3 1 0

來源：

2008年浙江大學計算機及軟件工程研究生機試真題

思路：

采用并查集求解。

對道路排序時，第一排序原則是道路是否已經修好，修好的排在前面，第二排序原則是道路的成本。

先計算已經修好的道路的連通性，然后逐個添加維修好的道路，添加過程中記錄新增道路的成本。最后的總成本就是答案。

代碼：

#include <stdio.h> #include <stdlib.h>#define N 100 #define M (N*(N-1)/2)typedef struct node {int x;int y;int d;int s; } ROAD; int n; int pre[N+1]; int count[N+1]; int num;void init() {for (int i=1; i<=n; i++){pre[i] = i;count[i] = 1;}num = n; } int find(int i) { while (i != pre[i]) i = pre[i];return i; } int combine(int i, int j) { int a = find(i); int b = find(j);if (a != b){ if (count[a] > count[b]){pre[b] = a;count[a] += count[b];count[b] = 0;}else{pre[a] = b;count[b] += count[a];count[a] = 0;}num --;return 1;}elsereturn 0; }int cmp(const void *a, const void *b) {ROAD *x = (ROAD *)a;ROAD *y = (ROAD *)b;if (x->s != y->s)return y->s - x->s;elsereturn x->d - y->d; }int main(void) {int m, i;ROAD r[M];int sum;while (scanf("%d", &n) != EOF && n){m = n*(n-1)/2;for(i=0; i<m; i++)scanf("%d%d%d%d", &r[i].x, &r[i].y, &r[i].d, &r[i].s);qsort(r, m, sizeof(r[0]), cmp);init();sum = 0;for(i=0; i<m; i++){ if(combine(r[i].x, r[i].y) && r[i].s == 0)sum += r[i].d;if (num == 1)break;} printf("%d\n", sum);} return 0; } /**************************************************************Problem: 1028User: liangrx06Language: CResult: AcceptedTime:20 msMemory:928 kb ****************************************************************/

轉載于:https://www.cnblogs.com/liangrx06/p/5084003.html

總結

以上是生活随笔為你收集整理的九度OJ 1028：继续畅通工程 （最小生成树）的全部內容，希望文章能夠幫你解決所遇到的問題。

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