題目描述
現在，你被委托在一個廣闊區域里面為某些確定的結點設計連接網路，首先，你會給定在區域里面的一系列結點，和連接這些結點的一組線路，對于每條可能使用的線路，你能得到鋪設該線路所需要的線纜長度，需要注意的是，在兩個給定的結點之間可能存在許多路徑，另外，假設給定的線路必定會連接（直接或間接）該區域里面的2個結點，
你的任務是為該區域設計一個網路，使得該區域中的任意2個結點之間都存在（直接或間接的）連接（也就是說，所有給定的結點之間都是連通的，但不一定存在直接相連的線路），同時，使得鋪設該網路的線纜總長度最小，
輸入格式
輸入由多個測驗構成，每個測驗定義一個要求的網路，每個測驗的第一個包含2個整數：第一個整數P給定區域內結點的數目，第二個整數R給出了線路的數目，接下來的R行，給出了兩個結點之間的線路，每行包含3個整數：前2個數字表示線路連接的結點，第三個整數表示鋪設該線路需要的線纜長度，每個整數之間用一個空格隔開，只給出一個整數P=0的測驗表示輸入結束，每個測驗之間用一個空行隔開，
輸入的最大的結點數目是50，給定的線路的最大長度是100，但是，可能存在的線路數目是無限的，給定的結點由整數1~P來標識（包含P），需要注意，結點i和j之間的線路可能由i到j的線路來表示，也可能由j到i的線路來表示，
輸出格式
對于每一個測驗，在單獨的一行輸出一個數字，表示為鋪設整個網路所需要的線纜總長度，
樣例輸入
1 0
2 3
1 2 37
2 1 17
1 2 68
3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32
5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12
0
樣例輸出
0
17
16
26
分析
即計算最小生成樹的權值（相關知識：Prim演算法和 Kruskal演算法）
代碼實作
#include <stdio.h>
#define MAXVERTEX 52
#define MAXEDGE 102
#define INF 1e7
//prim演算法計算最小生成樹的權值
int Prim(int matrix[][MAXVERTEX],int vnum, int ednum){
int mst = 0;
int isIntree[vnum+1] ;
for(int i = 0; i < vnum+1; i++)isIntree[i] = 0;
isIntree[1] = 1; //設定一個初始點
//遍歷vnum-1次，找出vnum-1個點
for(int i = 0; i < vnum-1; i++){
int min = INF;
int temp1,temp2;
for(int j = 1; j <= vnum; j ++){
for(int k = j+1; k <= vnum; k ++){
if(isIntree[j]*isIntree[k] == 0 && isIntree[j]+isIntree[k] == 1 ){
if(matrix[j][k]<min){
min = matrix[j][k];
temp1 = j;
temp2 = k;
}
}
}
}
mst = mst + min;
isIntree[temp1] = 1;
isIntree[temp2] = 1;
}
return mst;
}
int main(){
//輸入
int vnum; // 點數
int ednum; //邊數
while(scanf("%d",&vnum)!=EOF){
scanf("%d",&ednum);
if(vnum == 0)break;
if( ednum == 0 ){
printf("0\n");
continue;
}
//矩陣初始化
int matrix[MAXVERTEX][MAXVERTEX] ;
for(int i = 0; i <= vnum; i++){
for(int j = 0; j <= vnum; j++){
matrix[i][j] = INF;
}
}
//輸入邊 邊權 且 同一條邊只保留最小邊權
for(int i = 0; i < ednum; i++){
int v1,v2;
int tempweight;
scanf("%d",&v1);
scanf("%d",&v2);
scanf("%d",&tempweight);
if(tempweight < matrix[v1][v2]){
matrix[v1][v2] = tempweight;
matrix[v2][v1] = tempweight;
}
}
//prim演算法+輸出
printf("%d\n",Prim(matrix,vnum,ednum));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30680.html
標籤：C
上一篇：如何在沒有core檔案的情況下用dmesg+addr2line定位段錯誤
下一篇：C 實戰練習題目10