一：題目

某地區(qū)經(jīng)過(guò)對(duì)城鎮(zhèn)交通狀況的調(diào)查，得到現(xiàn)有城鎮(zhèn)間快速道路的統(tǒng)計(jì)數(shù)據(jù)，并提出“暢通工程”的目標(biāo)：使整個(gè)地區(qū)任何兩個(gè)城鎮(zhèn)間都可以實(shí)現(xiàn)快速交通（但不一定有直接的快速道路相連，只要互相間接通過(guò)快速路可達(dá)即可）。現(xiàn)得到城鎮(zhèn)道路統(tǒng)計(jì)表，表中列出了任意兩城鎮(zhèn)間修建快速路的費(fèi)用，以及該道路是否已經(jīng)修通的狀態(tài)。現(xiàn)請(qǐng)你編寫(xiě)程序，計(jì)算出全地區(qū)暢通需要的最低成本。

輸入格式:
輸入的第一行給出村莊數(shù)目N (1≤N≤100)；隨后的N(N?1)/2行對(duì)應(yīng)村莊間道路的成本及修建狀態(tài)：每行給出4個(gè)正整數(shù)，分別是兩個(gè)村莊的編號(hào)（從1編號(hào)到N），此兩村莊間道路的成本，以及修建狀態(tài) — 1表示已建，0表示未建。

輸出格式:
輸出全省暢通需要的最低成本。

輸入樣例:

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

輸出樣例:

3

二：思路

這個(gè)就是Prime算法的變型，我想的是如果這條路是已經(jīng)修過(guò)，那么的話(huà)就將其的權(quán)值你設(shè)為0

三:上碼

/**思路：如果是已經(jīng)修過(guò)，那么的話(huà)就將其的權(quán)值你設(shè)為0*/ #include<bits/stdc++.h> using namespace std;typedef struct GNode* PtrGraph;typedef struct GNode{int Nv;int Ne;int Data[105][105]; }gnode;int N; //利用鄰接矩陣儲(chǔ)存圖的基本信息 void CreateGraph(PtrGraph G){cin >> N;G->Nv = N;G->Ne = N*(N-1)/2;//矩陣初始化 for(int i = 1; i <= G->Nv; i++){for(int j = 1; j <= G->Nv; j++){G->Data[i][j] = 0; }}//矩陣賦值for(int i = 0; i < G->Ne; i++){int a,b,c,d;cin >> a >> b >> c >> d; if(d == 0){G->Data[a][b] = c;G->Data[b][a] = c; } } } //輸出矩陣 void print_Graph(PtrGraph G){for(int i = 1; i <= G->Nv; i++){for(int j = 1; j <= G->Nv; j++){cout << G->Data[i][j] << ' ';}cout << endl;} } //Prime最小成樹(shù)的算法 void Prime(PtrGraph G){int dist[105];int visited[105] = {0};int count = 0;for(int i = 1; i <= G->Nv; i++){dist[i] = G->Data[1][i];//將符號(hào)為1到其他點(diǎn)的距離存在 dist數(shù)組中 }visited[1] = 0;count++;while(1){int m = -1;int infinite = 9999;//求取最小值for(int i = 1; i <= G->Nv; i++){if(dist[i] < infinite && visited[i] != 1){infinite = dist[i];m = i;}}visited[m] = 1;count++;if(m == -1){break;} //更新for(int i = 1; i <= G->Nv; i++){if(visited[i] != 1 && G->Data[m][i] < dist[i] ){dist[i] = G->Data[m][i];}} } int sum = 0;for(int i = 1; i <= G->Nv; i++){sum += dist[i];}cout << sum;} int main(){PtrGraph G = (PtrGraph)malloc(sizeof(struct GNode));CreateGraph(G); // print_Graph(G);Prime(G);}

加油BOY！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

總結(jié)

以上是生活随笔為你收集整理的7-50 畅通工程之局部最小花费问题 (35 分)(思路加详解)来呀兄弟们冲呀呀呀呀呀呀呀的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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