题目传送门
记录详情

#include<bits/stdc++.h>
using namespace std;
int n,m,a[505][505],cnt,fa[505],tot;
long long ans;
struct str{
    int u,v,w;
}q[505];
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
bool cmp(str x,str y){return x.w<y.w;}
long long kru()
{
    int eu,ev;
    long long sum=0;
    sort(q+1,q+1+cnt,cmp);
    for(int i=1;i<=m;i++)
    {
        eu=find(q[i].u);
        ev=find(q[i].v);
        if(eu!=ev)
        {
            sum+=q[i].w;
            fa[ev]=eu;
        }
        if(++tot==m) break;
    }
    return sum;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            if(i<j&&a[i][j]!=0)
            {
                cnt++;
                q[cnt].u=i;
                q[cnt].v=j;
                q[cnt].w=a[i][j];
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        q[++cnt].u=0;
        q[cnt].v=i;
        q[cnt].w=n;
    }
    ans=kru();
    printf("%lld",ans);
    return 0;
}