```cpp
#include<iostream>
using namespace std;
int father[10001],f[1001][1001];
int find(int x)
{
while(x!=father[x]) x=father[x];
return x;
}
int main()
{
int n,t,now=0,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>t;
f[i][j]=t;
father[i]=i;
}
}
while(now<n-1)
{
int min=1e8,x,y,x1,y1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&f[i][j]>0&&f[i][j]<min)
{
min=f[i][j];
x=i;
y=j;
}
}
}
x1=find(x);
y1=find(y);
if(x1!=y1)
{
father[x1]=y1;
now++;
ans+=min;
}
f[x][y]=f[y][x]=0;
}
cout<<ans<<endl;
return 0;
}
```
这是我并查集做法,
~~可以赏脸看一看~~
by 微笑的坏坏 @ 2019-10-27 10:10:37
```cpp
#include<stdio.h>
#include<algorithm>
int n,i,F[100],Len,cnt;
struct Edge
{
int u, v, w;
}graph[5000];
int Find(int v)
{
if (F[v] != v)
return F[v] = Find(F[v]);
return F[v];
}
int main()
{
for (scanf("%d", &n); i < n; F[i] = i,i++)
for (int p = 0,temp; p < n; p > i ? graph[cnt].u = i, graph[cnt++].v = p++ : p++)
scanf("%d", p > i ? &graph[cnt].w : &temp);
std::sort(graph, graph + cnt, [](Edge e1, Edge e2) {return e1.w < e2.w; });
for (i = 0; i < cnt; ++i)
{
int uF = Find(graph[i].u), vF = Find(graph[i].v);
if (uF != vF)
{
Len += graph[i].w;
F[uF] = vF;
}
}
printf("%d", Len);
}
```
by adarion @ 2019-11-12 22:55:08