记录编号	595780	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	qyd	是否通过	通过
代码语言	C++	运行时间	1.291 s
提交时间	2024-10-16 22:01:06	内存使用	12.48 MiB

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1505;
const int MAXN=maxn*maxn;
int n,m,p[maxn],val[MAXN],r[MAXN];
int edge[maxn][maxn],u[MAXN],v[MAXN];
int cmp(int i,int j){return val[i]<val[j];}
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}//union-find set
void build(){
	int cnt=0;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    if(edge[i][j]!=-1)
	      {cnt++;u[cnt]=i;v[cnt]=j;val[cnt]=edge[i][j];}
	m=cnt;
	return ;
}
int Kruskal(){
	int ans=0;
	for(int i=0;i<n;i++)p[i]=i;//initialize the u-f set
	for(int i=0;i<m;i++)r[i]=i;//indirectedly sorting function
	sort(r,r+m,cmp);
	for(int i=0;i<m;i++){
		int d=r[i];int x=find(u[d]),y=find(v[d]);//find
		if(x!=y){ans+=val[d];p[x]=y;}//update and union
	}
	return ans;
}
int main()
{
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    cin>>edge[i][j];
	build();
	cout<<Kruskal()<<endl;
	return 0;
}