hdu 1875 暢通工程再續(kruskal || prim)

這道題目有點變化，條件是每條路的花費不能超過1000也不能小於10，否則不修該條路，所以呢，用kruskal最好，這種方法是檢查每一條邊，符合情況就加進去，否則就捨去，這樣最後判斷一下是不是所有的點都有一個共同的祖先就知道是不是連通圖。如果用prim算法的話，它每次選的是最小值，得判斷一下，實現起來比較麻煩。

代碼：（kruskal）

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 0x7fffffff 

using namespace std;
struct node
{
	int i,j;
	double len;
}gra[5500];
int p[105];
int cmp(const void *a,const void *b)
{
	return ((node *)a)->len - ((node *)b)->len >0 ? 1 : -1;
}
int find(int x)
{
	return x == p[x] ? x : p[x] = find(p[x]);
}
double dist(int a,int b,int c,int d)
{
	return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
double a[105],b[105];
int n; 
void kruskal()
{
	int i;
	double sum = 0;
	for(i=1; i<=n*(n-1)/2; i++)
	{
		int x = find(gra[i].i);
		int y = find(gra[i].j);
		if((x != y) && (gra[i].len >= 10)&&(gra[i].len<=1000))
		{
			sum += gra[i].len;
			p[x] = y;
		}
	}
	int flag = 0;
	for(i=1; i<=n; i++)
	{
		if(p[i]!=p[1])
		{
			flag = 1;
			break;
			
		}
	}
	sum*=100;
	if(flag)
		cout << oh! << endl;
	else
		printf(%.1lf
,sum);
}
int main()
{
	int T,i,j;
	cin >> T;
	while(T--)
	{
		int k = 1;
		cin >> n;
		for(i=1; i<=n; i++)
			cin >> a[i] >> b[i];
		for(i=1; i

普利姆算法實現了以下，wa了幾次，原因竟然是我把MIN定義成了整型。。。

注意判斷距離是否不小於10不大於1000

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 0x7fffffff

using namespace std;
double gra[105][105];
int a[105],b[105];
double dist(int a,int b,int c,int d)
{
	return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
int n;
void prim()
{
	int visit[105];
	memset(visit,0,sizeof(visit));
	int now,i,j;
	double MIN;	
	double d[105];
	for(i=1; i<=n; i++)
		d[i] = MAX;
	d[1] = 0;
	double sum = 0;
	now = 1,visit[1] = 1;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
			if(!visit[j] && d[j] > gra[now][j] &&(gra[now][j]>=10)&& (gra[now][j]<=1000))
				d[j] = gra[now][j];
		MIN = MAX;
		for(j=1; j<=n; j++)
		{
			if(!visit[j] && MIN > d[j])
				MIN = d[now = j];
		}
		visit[now] = 1;
	}
	int flag = 0;
	for(i=1; i<=n; i++)
	{
		sum += d[i];
		if(visit[i] == 0)
		{
			flag = 1;
			break;
		}
	}
	sum *= 100;
	if(flag)
		cout << oh! << endl;
	else
		printf(%.1lf
,sum);
}
int main()
{
	int T,i,j;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for(i=1; i<=n; i++)
			for(j=1; j<=n; j++)
				gra[i][j] = gra[j][i] = MAX;
		for(i=1; i<=n; i++)
			cin >> a[i] >> b[i];
		for(i=1; i