POJ 2421 Constructing Roads(Kruskal算法)

题意：给出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;

}