阅读原题

题目大意

给你几个（<=100）小岛的坐标，然后你把所有的岛都修上桥连接起来，求最小花费，还有个附加的限制：只有岛之间的距离大于等于10，或小于等于1000时才能修桥。

大概是因为十米以内不用建桥，千米以上无法建桥。哈哈，说着玩的。

很明显这是一道MST（最小生成树）的题目，貌似也有人用并查集AC过。

最小生成树算法

概述

最小生成树的常用算法有两个kruskal和prim算法。两者都是不停地执行归并操作，然而一言以蔽之，两者的不同之处在于：kruskal----归并边；prim----归并点

关于kruskal的题目原先AC过几道：

• hdu1301
• hdu1879
  
• hdu3371

prim算法

先贴一个维基百科的链接“prim算法”。下面我用离散数学来描述一下。

设有图G=（V，E），所有的结点集合为V，另有一空集合U。基本思路是：

1. 先随意确定一个起点。
2. 设此点为v，加入集合U中。
3. 观察与U中点相连的边，找到最短边。
4. 把与最短边另一端的点加入到集合U中。
5. 继续执行步骤3.知道V-U=0.即所有点都加入U中。

本题AC代码

朴素实现

这是最一般的实现方案。近乎模板的实现代码，在任一本数据结构书中可能都有提到。

void prim()
{
	double sum=0,lowcast[105]={0};
	int count=1;
	for(int i=0;i<c;i++)
	{
		lowcast[i] = d[0][i];
	}
	for(int i=0;i<c-1;i++)
	{
		double min = INF;//INF是自定义常量，表无穷大
		int k = 105;
		for(int j=0;j<c;j++)
			if(min>lowcast[j]&&lowcast[j])
			{
				min = lowcast[j];
				k = j;
			}
			if(k!=105)
			{
				sum+=lowcast[k];
				lowcast[k]=0;
				count++;
			}
			for(int j=0;j<c;j++)
				if(d[j][k]<lowcast[j])
				{
					lowcast[j] = d[j][k];
				}
	}
	if(count==c)
		printf("%.1lf\n",sum*100);
	else
		printf("oh!\n");
}

解释

二维数组d，保存着所有岛两两的距离。首先我们选择的起点是结点0.

for(int i=0;i<c;i++)
{
	lowcast[i] = d[0][i];
}

for(int i=0;i<c-1;i++)
{
	double min = INF;//INF是自定义常量，表无穷大，实际不可能为无穷大
	int k = 105;//初始化为105，因为实际不可能为105

	for(int j=0;j<c;j++)
		if(min>lowcast[j]&&lowcast[j])
		{
			min = lowcast[j];
			k = j;
		}

	if(k!=105)
	{
		sum+=lowcast[k];
		lowcast[k]=0;
		count++;
	}

	for(int j=0;j<c;j++)
		if(d[j][k]<lowcast[j])
		{
			lowcast[j] = d[j][k];
		}

完整AC代码

#include <iostream>
using namespace std;
#include <cmath>
const double INF=0x3f3f3f3f*1.0;
struct node
{
	int x;
	int y;
};

double d[105][105];
int c;//岛屿个数
void prim()
{
	double sum=0,lowcast[105]={0};
	int count=1;
	for(int i=0;i<c;i++)
	{
		lowcast[i] = d[0][i];
	}
	for(int i=0;i<c-1;i++)
	{
		double min = INF;//INF是自定义常量，表无穷大
		int k = 105;
		for(int j=0;j<c;j++)
			if(min>lowcast[j]&&lowcast[j])
			{
				min = lowcast[j];
				k = j;
			}
		if(k!=105)
		{
			sum+=lowcast[k];
			lowcast[k]=0;
			count++;
		}
		for(int j=0;j<c;j++)
			if(d[j][k]<lowcast[j])
			{
				lowcast[j] = d[j][k];
			}
	}
	if(count==c)
		printf("%.1lf\n",sum*100);
	else
		printf("oh!\n");
}
int main()
{

	int t;
	cin>>t;
	while(t--)
	{
		node n[105];
		cin>>c;
		for(int i=0;i<c;i++)
			cin>>n[i].x>>n[i].y;
		for(int i=0;i<c;i++)
			for(int j=0;j<c;j++)
			{
				if(i==j)
				{		
					d[i][j]=0;
					continue;
				}

				int x1=n[i].x, x2=n[j].x;
				int y1=n[i].y, y2=n[j].y;
				double dist=sqrt(1.0*(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
				if(dist<10.0||dist>1000.0)
					d[j][i]=d[i][j]=INF;
				else
					d[j][i]=d[i][j]=dist;
			}
			prim();
	}
	return 0;
}

其他注释

const double INF=0x3f3f3f3f*1.0;

在计算岛与岛之间距离的时候。

    if(i==j)
    {        
        d[i][j]=0;
        continue;
    }