zoj 1203 Swordfish prim算法

#include "stdio.h".
#include <iostream>
#include<math.h>
using namespace std;
double dis[105][105];
double p[105][2];//点的坐标
double ans;//最短距离
int n;
void makedis()//算出两个点之间的距离
{
	int i, j; double r;
	for (i = 0; i < n; i++)
	for (j = i; j <n; j++)
	{
		r = sqrt((p[i][0] - p[j][0])*(p[i][0] - p[j][0]) + (p[i][1] - p[j][1])*((p[i][1] - p[j][1])));
		dis[i][j] = r;// i 点到j 点 的距离
		dis[j][i] = r;
	}
}

void prim()
{
	int temp[105];  //存放已经加入的结点
	int size;    // 已加入的结点个数
	int i, j, k;
	int curnode, pos2;
	double min;

	temp[0] = 0;
	size = 1;

	dis[0][0] = 1;

	for (i = 0; i < n - 1; i++)//执行n-1次将所有的点访问完
	{
		min = 32767; // 极大值
		for (j = 0; j < size; j++)
		{
			curnode = temp[j];
			for (k =0; k < n; k++)
			if (dis[curnode][k] <= min && dis[k][k] == 0) //min 为当前最小值，为0表示没有访问过，如果新加入结点后有再小的边就将对应的点加入
			{
				min = dis[curnode][k];
				pos2 = k;
			}
		}
		ans += min;
		dis[pos2][pos2] = 1;
		temp[size] = pos2; size++;

	}
}


int main()//主程序
{
	int  step; 
	int i;
	step = 0;
	while (scanf("%d", &n))//输入点的个数，为0时结束
	{
		step++;
		ans = 0;//距离总和
		if (n == 0) break;
		if (step != 1)printf("\n");
		for (i = 0; i <n; i++)//输入n 个点的坐标
		{
			scanf("%lf%lf", &p[i][0], &p[i][1]);
		}
		makedis();
		prim();
		printf("Case #%d:\n", step);
		printf("The minimal distance is: %.2lf\n", ans);
	}
	return 0;
}
题目
zoj 1203 Swordfish prim算法

推荐阅读
