题意：给出n个村庄之间的距离，再给出已经连通起来了的村庄。求把所有的村庄都连通要修路的长度的最小值。

思路：Kruskal算法

课本代码：

//Kruskal算法#include<iostream>using namespace std;int fa[120];int get_father(int x){	return fa[x]=fa[x]==x?x:get_father(fa[x]);//判断两个节点是否属于一颗子树（并查集）}int main(){	int n;	int p[120][120];	while(scanf("%d",&n)!=EOF){		int i,j,k,m;		for(i=0;i<n;i++)			for(j=0;j<n;j++)				scanf("%d",&p[i][j]);			for(i=0;i<n;i++) fa[i]=i;			scanf("%d",&m);			while(m--){				int a,b;				scanf("%d%d",&a,&b);				fa[get_father(a-1)]=get_father(b-1);// a  合并到 b			}			int ans=0;			for(k=1;k<=1000;k++)// kruskal 算法，这里每个长度都进循环，若加一个长度存在的标记，可以节省时间				for(i=0;i<n;i++)					for(int j=0;j<n;j++)						if(p[i][j]==k &&get_father(i)!=get_father(j)){							fa[fa[i]]=fa[j];//合并两颗子树（并查集）							ans+=k;						}			printf("%d\n",ans);	}	return 0;}

代码2：加了mark标记长度是否存在，代码中-------------为添加部分

//Kruskal算法#include<iostream>using namespace std;int fa[120];int mark[1010];//-------------标记长度是否存在int get_father(int x){	return fa[x]=fa[x]==x?x:get_father(fa[x]);//判断两个节点是否属于一颗子树（并查集）}int main(){	int n;	int p[120][120];	while(scanf("%d",&n)!=EOF){		memset(mark,0,sizeof(mark));		int i,j,k,m;		for(i=0;i<n;i++)			for(j=0;j<n;j++){				scanf("%d",&p[i][j]);				mark[p[i][j]]=1;//-------------把当前的长度标记一下			}			for(i=0;i<n;i++) fa[i]=i;			scanf("%d",&m);			while(m--){				int a,b;				scanf("%d%d",&a,&b);				fa[get_father(a-1)]=get_father(b-1);// a  合并到 b			}			int ans=0;			for(k=1;k<=1000;k++)// kruskal 算法				if(mark[k]){// -------------------长度存在的时候，再进入这个循环									for(i=0;i<n;i++)						for(int j=0;j<n;j++)							if(p[i][j]==k &&get_father(i)!=get_father(j)){								fa[fa[i]]=fa[j];//合并两颗子树（并查集）								ans+=k;							}				}				printf("%d\n",ans);	}	return 0;}