uva 10034 Freckles (kruskal||prim)

题目上仅仅给的坐标，没有给出来边的长度，不管是prim算法还是kruskal算法我们都须要知道边的长度来操作。

这道题是浮点数，也没啥大的差别，处理一下就能够了。

有关这两个算法的介绍前面我已经写过了。就不在多写了

prim算法：

<span style="font-family:Courier New;font-size:18px;">#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<vector>

#include<set>

#include<string>

#include<algorithm>

#include<climits>

using namespace std;

struct node

{

	double i,j;

}g[105];

double gra[105][105];

double dist(double a,double b,double c,double d)

{

	return sqrt((a-c)*(a-c)+(b-d)*(b-d));

}

int n,cnt=0,T;

void prim()

{

	int visit[105],now,i,j;

	double dis[105];

	double Min;

	memset(visit,0,sizeof(visit));

	for(i=1; i<=n; i++)

		dis[i] = INT_MAX;

	visit[1] = 1, dis[1] = 0, now = 1;//now都是当前新加的点

	for(i=1; i<=n; i++)

	{

		for(j=1; j<=n; j++)

		{

			if(!visit[j] && dis[j]>gra[now][j])//用新加的点来更新其它点到此集合的距离

				dis[j] = gra[now][j];

		}

		Min = INT_MAX;

		for(j=1; j<=n; j++)

		{

			if(!visit[j] && dis[j] < Min)//每次都找到距离最小的点。加进去

				Min = dis[now = j];

		}

		visit[now] = 1;

	}

	double sum = 0;

	for(i=1; i<=n; i++)

	{

		sum += dis[i];

	}

	printf("%.2lf\n",sum);

	if(cnt!= T)//注意每两个输出案例之间都有一个换行

		cout << endl;

}

int main()

{

	int i,j;

	cin >> T;

	while(cin >> n)

	{

		cnt ++;

		for(i=1; i<=n; i++)

		{

			cin >> g[i].i >> g[i].j;

		}

		memset(gra,0,sizeof(gra));

		for(i=1; i<=n; i++)

		{

			for(j=i+1; j<=n; j++)

			{

				gra[i][j] = gra[j][i] = dist(g[i].i,g[i].j,g[j].i,g[j].j);

			}

		}

		prim();

	}

	return 0;

}

</span>

kruskal算法:

<span style="font-family:Courier New;font-size:18px;">#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<vector>

#include<set>

#include<string>

#include<algorithm>

#include<climits>

using namespace std;

struct node

{

	int i,j;

	double len;

}gra[10005];

struct node1

{

	double i,j;

}g[105];

int p[105];

double dist(double a,double b,double c,double d)

{

	return sqrt((a-c)*(a-c)+(b-d)*(b-d));

}

int cmp(const void *a,const void *b)

{

	return (((node *)a)->len - ((node *)b)->len > 0) ? 1:-1;

}

int n,cnt=0,T,k;

int find(int x)

{

	return x == p[x]?

x: p[x] = find(p[x]);

}

void kruskal()

{

	double sum = 0;

	int i;

	for(i=1; i<k; i++)

	{

		int x = find(gra[i].i);

		int y = find(gra[i].j);

		if(x!=y)

		{

			sum += gra[i].len;

			p[x] = y;

		}

	}

	printf("%.2f\n",sum);

	if(cnt != T)

		cout << endl;

}

int main()

{

	int i,j;

	cin >> T;

	while(cin >> n)

	{

		cnt ++;

		for(i=1; i<=n; i++)

		{

			cin >> g[i].i >> g[i].j;

		}

		memset(gra,0,sizeof(gra));

		k=1;

		for(i=1; i<=n; i++)

		{

			for(j=i+1; j<=n; j++)

			{

				gra[k].len = dist(g[i].i,g[i].j,g[j].i,g[j].j);

				gra[k].i = i;

				gra[k].j = j;

				k++;

			}

		}

		//prim();

		for(i=1; i<=n; i++)

			p[i] = i;

		qsort(gra+1,k-1,sizeof(gra[0]),cmp);

		kruskal();

	}

	return 0;

}

</span>