題目描述

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

輸入

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

當N為0時輸入結束。

輸出

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

樣例輸入

4 1 2 1 1 1 3 6 0 1 4 2 1 2 3 3 0 2 4 5 0 3 4 4 0 3 1 2 1 1 2 3 2 1 1 3 1 0 0

樣例輸出

3 0

WA原因：運行錯誤50%，還是數組越界的原因...?

#include <iostream> #include <algorithm> #include <vector>using namespace std;const int maxn = 100+10; const int inf = 1000000000;int a; //村莊數目//kruskal struct edge {int u, v, dis, state; }E[maxn];int father[maxn]; int find_father(int x) {int a = x;while(x != father[x]){x = father[x];}while(a != father[a]){int z = a;a = father[a];father[z] = x;}return x; }bool cmp(edge a, edge b) {return a.dis < b.dis; }int kruskal(int n, int m) {int ans1 = 0, num_edge = 0;for(int i = 1; i <= n; i++){father[i] = i;}for(int i = 0; i < m; i++){if(E[i].state == 1) //建好了{int u = E[i].u;int v = E[i].v;father[find_father(u)] = find_father(v);num_edge++;}}sort(E, E+m, cmp);for(int i = 0; i < m; i++){int fa = find_father(E[i].u);int fb = find_father(E[i].v);if(fa != fb){father[fa] = fb;ans1 += E[i].dis;num_edge++;if(num_edge == n - 1) break;}}if(num_edge != n - 1){return -1;}else return ans1; }int main() {while(scanf("%d", &a) != 0){int b = a * (a-1) / 2;for(int i = 0; i < b; i++){scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].dis, &E[i].state);}int ans = kruskal(a, b);if(ans == -1) break;else printf("%d\n", ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的Codeup墓地-问题 D: 继续畅通工程的全部內容，希望文章能夠幫你解決所遇到的問題。

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