记录编号	554810	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	数声风笛ovo	是否通过	通过
代码语言	C++	运行时间	1.157 s
提交时间	2020-09-21 18:29:23	内存使用	24.00 MiB

#include<bits/stdc++.h>
#define pp cout<<m
using namespace std;
const int maxn=1e3+5,maxe=3e6+1;
struct node{
	int from,to,c;
}e[maxe];
int m=0,n;
void build (int from,int to,int c){
	e[++m].from=from;
	e[m].to=to;
	e[m].c=c;
}
int fa[maxn]={0};
int find(int x){
    if(x!=fa[x])
		return fa[x]=find(fa[x]);
    return fa[x];
}
void add(int t1,int t2){
	fa[find(t1)]=find(t2);
}
bool cmp(node p1,node p2){
	return p1.c<p2.c;
}
int main(){
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	int ans=0;
	scanf("%d",&n);int p;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&p);
			if(p!=-1) build(i,j,p);
		}
	}
	sort(e+1,e+m+1,cmp);
	int built=0;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		if(find(e[i].from)!=find(e[i].to)){
			add(fa[e[i].from],fa[e[i].to]);
			ans+=e[i].c;
			built++;
		}
		if(built==n-1) break;
	}
	printf("%d\n",ans);
	return 0;
}