Problem A: 调试程序
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:34
Solved:3
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