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