閱讀原題

題目大意

給你幾個（<=100）小島的坐標，然後你把所有的島都修上橋連接起來，求最小花費，還有個附加的限制：只有島之間的距離大於等於10，或小於等於1000時才能修橋。

大概是因為十米以內不用建橋，千米以上無法建橋。哈哈，說著玩的。

很明顯這是一道MST（最小生成樹）的題目，貌似也有人用並查集AC過。

最小生成樹算法

概述

最小生成樹的常用算法有兩個kruskal和prim算法。兩者都是不停地執行歸並操作，然而一言以蔽之，兩者的不同之處在於：kruskal----歸並邊；prim----歸並點

關於kruskal的題目原先AC過幾道：

prim算法

先貼一個維基百科的鏈接“prim算法”。下面我用離散數學來描述一下。

設有圖G=（V，E），所有的結點集合為V，另有一空集合U。基本思路是：

本題AC代碼

樸素實現

這是最一般的實現方案。近乎模板的實現代碼，在任一本數據結構書中可能都有提到。

void prim()
{
	double sum=0,lowcast[105]={0};
	int count=1;
	for(int i=0;ilowcast[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;ilowcast數組保存的是集合U中的點到V-U中每個結點的最近距離。一開始的時候，集合U中只有結點0，所以lowcast數組保存的都是結點0到每個結點的距離。


for(int i=0;i這是prim算法的主要部分開始了，初始化min用於保存到集合U中的點最小距離的邊的長度。k就是用於保存最短邊的另一端的結點名稱。


	for(int j=0;jlowcast[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;ilowcast[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;i1000.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不了的。大家具體方案具體分析啦。