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算法

最新文章

热门文章
