John的农场（最小生成树）

45 阅读 0 评论 30 点赞

我是靠谱客的博主听话黑裤，最近开发中收集的这篇文章主要介绍John的农场（最小生成树），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

John是一个农场主，他有几个牧场，为了好好照顾他的牛，他必须在几个牧场之间来回，可糟糕的天气往往使得道路非常泥泞，为此John准备在牧场之间铺一些石子路，这样在下雨天也能快速地从一个牧场到另外一个牧场。但John的资金有限，为了自己能从任一个牧场都通过石子路到达另外一个牧场，他需要好好设计一下线路。请帮助John设计好线路，使得John能从任一个牧场都通过石子路到达另外一个牧场，且线路的费用最低。

输入：

第一行是一个整数K，表示有多少个测试用例，以后每个测试用例占n+1行。每个测试用例的第一行为一个整数n（3<=n<=20），表示有多少个牧场，从第二行开始为一个n*n的矩阵，矩阵元素aij表示从i个牧场到j个牧场的铺路费用。

输出：

每行输出一个测试用例的最小铺路费用。

Sample Input

2
6
0 6 1 5 0 0
6 0 5 0 3 0
1 5 0 5 6 4
5 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0
4
0 1 2 3
1 0 3 4
2 3 0 1
3 4 1 0

Sample Output

15
4

感悟：有的时候看书不是最好的选择。自己看算法书，一个算法看半天，还不一定能实现或者实现的特别复杂。而看视频的话很容易理解，省了很多时间。

***prime算法实现，复杂度O(n*n)
#include<stdio.h>
#define inf 0x3f3f3f3f
typedef struct NODE node;
struct NODE{
	int vex;//该牧场close[i]与谁相连
	int mincost;//相连最小的路径
};
node close[25];//下标就是牧场序号
int findmin(int n)//找到最小的花费路径,路径为i到close[i].vex
{
	int tep;
	int min=inf;
	for(int i=1;i<=n;i++)
	{
		if(close[i].mincost!=0)
		{
			if(close[i].mincost<min)
			{
				min=close[i].mincost;
				tep=i;
			}
		}	
	} 
	return tep;
}
int main(void)
{
	int k;
	scanf("%d",&k);
	while(k--)
	{
		int n;
		int ans=0;
		int cost[22][22]={0};
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				scanf("%d",&cost[i][j]);
				if(cost[i][j]==0) cost[i][j]=inf;
			}
		}
		close[1].mincost=0;//此点用过,就是已经加入到了生成树里面
		//默认1为起始点
		for(int i=2;i<=n;i++)//初始化数组，
		//把所有cost数组第一行的数据复制到close数组里
		{
			close[i].vex=1;
			close[i].mincost=cost[1][i];
		}
		for(int i=1;i<n;i++)//执行次数
		{
			int tep=findmin(n);	//找到花费最小路径的下标
			ans+=close[tep].mincost;//答案加上
			close[tep].mincost=0;//更新为此点用过
			for(int i=1;i<=n;i++) //更新close数组的值，
			//看看有没有其他未用过的点（牧场）到tep的路径<其他未用过的点到生成树里面其他点的路径
			{
				if(close[i].mincost!=0&&cost[tep][i]<close[i].mincost)
				{
					close[i].mincost=cost[tep][i];
					close[i].vex=tep;
				}
			}
		} 
		printf("%dn",ans);
	}
}