记录编号	598203	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	chenbp	是否通过	通过
代码语言	C++	运行时间	1.289 s
提交时间	2025-01-22 17:15:58	内存使用	8.33 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct edge{
    int u,v,w;
}e[2253100];
int fa[1510];
int fi(int x){
    if(x==fa[x]) return x;
    return fa[x]=fi(fa[x]);
}
bool cmp(edge x,edge y){
    return x.w<y.w;
} 
int main(){
    freopen("mcst.in","r",stdin);
    freopen("mcst.out","w",stdout);
    int n;
    cin>>n;
    int num=0;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int v;
            cin>>v;
            if(v!=-1){
                num++;
                e[num].u=i;
                e[num].v=j;
                e[num].w=v;
            }
        }
    }
    sort(e+1,e+1+num,cmp);
    long long ans=0;
    for(int i=1;i<=num;i++){
        int x=fi(e[i].u),y=fi(e[i].v);
        if(x!=y){
            ans+=e[i].w;
            fa[x]=y;
        } 
    }
    cout<<ans;
    return 0;
}