当前位置:首页 > 资讯 > 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算法

推荐文章
编辑推荐
普利姆算法,是一种常用的求最小生成树的算法。 最小生成树,使得一个连通图内拥有最小的和。对现实
借用一张图片说明: code: #include <iostream> using namespace std; #define MAX 1000 int
参考维基百科与《算法导论》 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索
最小生成树的Prim算法也是贪心算法的一大经典应用。Prim算法的特点是时刻维护一棵树,算法不断加边
最小生成树 3条构造最小生成树的准则: 只能使用该网络中的边来构造最小生成树 只能使用恰好n-1条边
Prim算法和Kruskal算法都能从连通图找出最小生成树。区别在于Prim算法是挨个找,而Kruskal是先排序
最小生成树是数据结构中图的一种重要应用,它的要求是从一个带权无向完全图中选择n-1条边并使这个
Prim算法和Kruskal算法都能从连通图找出最小生成树。区别在于Prim算法是挨个找,而Kruskal是先排序
Prim算法和Kruskal算法都能从连通图找出最小生成树。区别在于Prim算法是挨个找,而Kruskal是先排序
普里姆(Prim)算法   1.基本思想:设G=(V, E)是具有n个顶点的连通网,T=(U, TE)是G的最小生成树
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号