阅读原题

题目大意

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

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

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

最小生成树算法

概述

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

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

hdu1301hdu1879
hdu3371

prim算法

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

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

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

本题AC代码

朴素实现

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

void prim()
{
	double sum=0,lowcast[105]={0};
	int count=1;
	for(int i=0;i
  
   lowcast[j]&&lowcast[j])
			{
				min = lowcast[j];
				k = j;
			}
			if(k!=105)
			{
				sum+=lowcast[k];
				lowcast[k]=0;
				count++;
			}
			for(int j=0;j
    
     
    解释 
    二维数组d，保存着所有岛两两的距离。首先我们选择的起点是结点0. 
     
    for(int i=0;i
     
      lowcast数组保存的是集合U中的点到V-U中每个结点的最近距离。一开始的时候，集合U中只有结点0，所以lowcast数组保存的都是结点0到每个结点的距离。

      

      

      for(int i=0;i
       
        这是prim算法的主要部分开始了，初始化min用于保存到集合U中的点最小距离的边的长度。k就是用于保存最短边的另一端的结点名称。

        







        

        	for(int j=0;j
         
          lowcast[j]&&lowcast[j])
		{
			min = lowcast[j];
			k = j;
		}
         这里也比较好理解，就是在不停的更新最短边的长度及最短边的另一端结点名。注意lowcast[j]==0时，表示结点
         j 已经加入集合U了。

        

        

        	if(k!=105)
	{
		sum+=lowcast[k];
		lowcast[k]=0;
		count++;
	}如果k!=105，表示确实找到了最短边。所以把这条边的长度lowcast[k]加入到总和sum中，同时标记该点k已经加入集合U，即lowcast[k]=0。count用于记录已加入集合U中的点的个数。

        

        

        	for(int j=0;j
         
          因为集合U中的点可能已经增加了，所以集合U中的点到V-U的点的最近距离也要再次更新。这个操作被称为 
          “松弛操作”。在图论问题中有较多应用。
          


          

          完整AC代码

          

          #include 
           
            
using namespace std;
#include 
            
              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
             
              lowcast[j]&&lowcast[j]) { min = lowcast[j]; k = j; } if(k!=105) { sum+=lowcast[k]; lowcast[k]=0; count++; } for(int j=0;j
              
               >t; while(t--) { node n[105]; cin>>c; for(int i=0;i
               
                >n[i].x>>n[i].y; for(int i=0;i
                
                 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;自定义表示无穷大的double常量。关于这个值的选取可以参考这篇文章《
          编程中无穷大常量的设定技巧》。

          

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

          

              if(i==j)
    {        
        d[i][j]=0;
        continue;
    }表示如果是i==j，就直接设为0，在prim算法里对应lowcast也会是0，会被忽略掉。我这里不能设成INF，我的实现方案中INF会导致AC不了的。大家具体方案具体分析啦。

hdu1875浅谈prim算法的朴素实现