记录编号	47786	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	1.600 s
提交时间	2012-11-03 14:29:15	内存使用	0.32 MiB

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 2000;
int n, t, s;
vector<int> G[N], c[N];
bool l[N];
void Prim() {
    priority_queue<pair<int, int> > q;
    l[1] = 1; q.push(make_pair(0, 1));
    for(int k=1; k<n; k++) {
        int u = q.top().second; q.pop();
        for(int i=0; i<G[u].size(); i++)
            if(!l[G[u][i]])
                q.push(make_pair(-c[u][i], G[u][i]));
        while(!q.empty() && l[q.top().second])
            q.pop();
        l[q.top().second] = 1;
        s += -q.top().first;
        q.pop();
    }
}
int main() {
    freopen("mcst.in", "r", stdin);
    freopen("mcst.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) {
            scanf("%d", &t);
            if(t < 0) continue;
            G[i].push_back(j); c[i].push_back(t);
            G[j].push_back(i); c[j].push_back(t);
        }
    Prim();
    printf("%d\n", s);
    return 0;
}