```c
#include<bits/stdc++.h>
using namespace std;
int fa[300010];
struct Edge{
int x,y,dis;
}E[600010];
int n,m,tot,sum;
int get(int x){
if (fa[x]==x) return x;
return fa[x]=get(fa[x]);
}
void merge(int x,int y){
if (get(x)!=get(y)){
fa[get(x)]=y;
}
}
bool cmp(Edge x,Edge y){
if (x.dis>y.dis) return 0;
else return 1;
}
int read()
{
int ans=0,flag=1;
char ch=getchar();
while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
if(ch=='-') flag=-1,ch=getchar();
while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
return ans*flag;
}
int main()
{
n=read(),m=read();
for (int i=1;i<=m;i++){
fa[i]=i;
}
int tot=0;
for (int i=1;i<=m;i++){
for (int j=1;j<=m;j++){
int dis=read();
if (dis!=0&&dis<n)
E[++tot].x=i,E[tot].y=j,E[tot].dis=dis;
}
}
sort(E+1,E+tot+1,cmp);
for (int i=1;i<=tot;i++){
if (get(E[i].x)!=get(E[i].y)&&E[i].dis!=0)
merge(E[i].x,E[i].y),sum+=E[i].dis;
}
for (int i=1;i<=m;i++){
if (fa[i]==i) sum+=n;
}
cout<<sum<<endl;
return 0;
}
```
by Lovable_Wind @ 2021-10-07 21:37:03
最后的点可能优惠完比之前贵，re是因为矩阵5000*5000=25000000，要开这么大
by shark_big @ 2021-11-04 09:46:59