是 prim 算法

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5050;
const int M=2e5+5;
const int INF=0x3f;
int n,m,cnt,num,sum,val[N],head[N],vis[N],ans;
struct node{
    int to,next,val;
}a[M<<1];
struct edge{
    int pos,val;
    bool operator<(const edge &a)const{
        return val>a.val;
    }
};
void add(int u,int v,int w){
	++cnt;
	a[cnt].to=v;
	a[cnt].next=head[u];
	a[cnt].val=w;
	head[u]=cnt;
}
inline void prim(){
	priority_queue<edge>q;
	memset(val,INF,sizeof(val));
	val[1]=0;
	q.push((edge){1,0});
	while(!q.empty()&&num<n){
		edge now=q.top();q.pop();
		int x=now.pos;
		if(vis[x])continue;
		vis[x]=1;++num;sum+=now.val;
		for(int i=head[x];i;i=a[i].next){
			int v=a[i].to;
			if(val[v]>a[i].val){
				val[v]=a[i].val;
				if(!vis[v])q.push((edge){v,a[i].val});
			}
		}
	}
}
signed main(){
	int k;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>k;
			if(i<j){
				add(i,j,k);
				add(j,i,k);
			}
		}
	}
	prim();
    for(int i=1;i<=n;i++){
    	ans+=val[i];
	}
	cout<<ans;
	return 0;
}