克鲁斯卡尔求最小生成树思想:首先将n个点看作n个独立的集合,将所有边快排(从小到大)。然后,按排好的顺序枚举每一条边,判断这条边连接的两个点是否属于一个集合。若是,则将这条边加人最小生成树,并将两个点所在的集合合并为一个集合。若否，则跳过。直到找到n-1条边为止。

#include<iostream>

#include<algorithm>

using namespace std;

struct point{

int x;int y;int vi

point a[10000];

int cmp(const point &a,const point &b){)return 1;

if(1）

else return 0

int fat[101];

int father(int x){

if(fat[x】!-x)return fat[x]②

else return fatlx]i

void unionn(int x,int y){int famfather(x):int fb father(y);

if(fa! fb) fat[ fa].fb;

int main(){

int i,j，n,m，km0,ans=0,cnt=0;

cin>>n;

for(i=1;i<=n;i++)

for(j=l;j<=n;j++)

cin>>m;

if(m!.0){

k++;

a[k].x-i;

a[k].y-j;

a[ k].v=m;

sort(a+1,a+1+k,③);

for(i-l;i<=n;i++){

fat[i]=i;

£or(iml;i<mk;i++){

if(father(a[i].x)!= ④){ans+ a[i].v;unionn (a[i].x,a[i].y);

cnt++;

if(5)break;

cout<<ans;

return 0;