當前位置:首頁 > 資訊 > info6 > 正文

zoj 1203 Swordfish prim算法

發表于: 2014-04-20   作者:chen_xinjia   來源:轉載   瀏覽:
摘要: #include"stdio.h". #include #include usingnamespacestd; doubledis[105][105]; doublep[105][2];//點的坐標 doubleans;//最短距離 intn; voidmakedis()//算出兩個點之間的距離 { inti,j;doubler; for(i=0;i
#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算法

版權所有 IT知識庫 CopyRight ? 2009-2015 IT知識庫 IT610.com , All Rights Reserved. 京ICP備09083238號
广东25选5开奖结果