POJ 1258 Agri-Net（Prim算法）

题意：n个农场，求把所有农场连接起来所需要最短的距离。

思路：prim算法

课本代码：

//prim算法

#include<iostream>

#include<stdio.h>

#include<cstring>

using namespace std;

int n;

int tot;

int v[150][150];

int dist[150];//存 节点到树 的最小距离

bool use[150];//标记节点是否存在

int main(){

	while(scanf("%d",&n)!=EOF){

		memset(use,false,sizeof(use));//初始化节点 都存在

		tot=0;

		use[0]=1;

		int i,j,k;

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

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

				scanf("%d",&v[i][j]);

			dist[0]=0x7FFFFFFF;//赋值为最大值

			for(i=1;i<n;i++)//初始距离

				dist[i]=v[0][i];

			for(i=1;i<n;i++){//连接 剩下的 n-1个节点

				int tmp=0;

				for(k=1;k<n;k++)//找到最短的距离 节点

					if(dist[k]<dist[tmp] &&!use[k]) tmp=k;

					tot +=dist[tmp];// 加到 总距离中

					use[tmp]=true;

					for(k=1;k<n;k++)//调整距离

						if(!use[k])

							dist[k]=v[k][tmp]<dist[k]?v[k][tmp]:dist[k];

			}

			printf("%d\n",tot);

	}

	return 0;

}

另外，这道题也可以用 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];

	int mark[100100];

	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;

			int ans=0;

			for(k=1;k<=100000;k++)// kruskal 算法

				if(mark[k]){//  若不加mark ，会超时

				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;

}

巴特西

POJ 1258 Agri-Net（Prim算法）

最新文章

热门文章