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