1953: 调试程序
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:35
Solved:4
Description
少年宫有 n 台计算机,现要将它们用数据线连接起来组成网。由于计算机所处的位置不同,因此不同的两台计算机的连接所化费的金额是不同的。当然,整个少年宫n台计算机都用数据线连接,其连接费用如下带权邻接矩阵g表示。为了节省费用,少年宫马老师需要在图g上规划最佳的连接方案,请你帮助实现这n台计算机的连接的最少化费方案(不管是直接的或间接的)。
请调试以下程序找出错误后上传。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int prim(vector<vector<int>> & graph,int n) {
vector<int> key(n INT_MAX); vector<int> parent(n -1);
key[0] = 0;
for (int i = 0; i < n; i++) {
int u = min_element(key.begin(),key.end()) - key.begin();
if (key [ u ] == INT_MAX)
break;
for (int v = 0; v < n; v++) {
if (graph[ u ][ v ] != 0 && key[ v ] > graph[ u ][ v ]) {
key[ v ] = graph[ u ][ v ];
parent[ v ] = u;
}
}
}
int sum = 0;
for (int i = 0; i < n; i++) {
if (parent[ i ] != -1) {
#ifdef DEBUG
cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << endl;
#endif
sum += key[i];
}
}
return sum;
}
int main() {
int n,m;
cin >> n >> m;
vector<vector<int>> graph(n vector<int>(n 0));
for (int i = 0; i < m; i++) {
int u,v,w; cin >> u >> v >> w;
graph[ u ][ v ] = w;
graph[ v ][ u ] = w;
}
int result = prim(graph n);
cout << result << endl;
return 0;
}
Input
第一行为整数n(2<=n<=100),表示计算机的数目。此后的n行为图 g的二维数据,整数表示直接连接第 i台计算机和第 j台计算机的费用。数字间空格分隔。
Output
一个正整数,表示连接最优方案的费用。
Sample Input Copy
5
0 3 0 5 0
3 0 6 2 6
0 6 0 0 5
5 2 0 0 8
0 6 5 8 0
Sample Output Copy
16
HINT
2<=n<=100