当前位置:首页 > 资讯 > info6 > 正文

ZOJ 2048 highways

发表于: 2014-05-10   作者:chen_xinjia   来源:转载   浏览:
摘要: 题目比我想象地要容易很多。。一开始想得太复杂了,本来想试一下kruskal算法的,嫌麻烦。。还是用了之前1203的prim算法。。。以为要注意这道题的输出顺序,结果不用,直接输出就可以了,就是注意一下空行的输出就行了//#include"stdafx.h" #include #include"stdio.h" #include usingnamespacestd; inttown[750][2];

题目

比我想象地要容易很多。。一开始想得太复杂了,本来想试一下kruskal算法的,嫌麻烦。。还是用了之前1203的prim算法。。。以为要注意这道题的输出顺序,结果不用,直接输出就可以了,就是注意一下空行的输出就行了

//#include "stdafx.h"
#include <iostream>
#include "stdio.h"
#include <math.h>
using namespace std;
int town[750][2];
double dis[750][750];
double ans;
int n;
void prim()
{
	int temp[750];  //存放已经加入的结点  
	int size;    // 已加入的结点个数  
	int i, j, k;
	int lastnode1 = 0, 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];
				lastnode1 = curnode;

				pos2 = k;
			}
		}
		if (min != 0)
		{

			cout << lastnode1 + 1 << " " << pos2 + 1 << endl;//ans += min;
		}
		dis[pos2][pos2] = 1;//表示已经访问过
		temp[size] = pos2; size++;

	}
}
int main()
{
	int T, M = -1, E;
	cin >> T;
	while (T--)
	{
		memset(dis, 0, sizeof(dis));
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			cin >> town[i][0] >> town[i][1];//输入town 的坐标
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)//计算每两个点之前的距离
			{

				dis[j][i] = dis[i][j] = sqrt(pow(town[i][0] - town[j][0], 2) + pow(town[i][1] - town[j][1], 2));        //计算两点间的距离  
			}
		}
		cin >> E;
		int x, y;
		while (E--)
		{
			cin >> x >> y;
			dis[x - 1][y - 1] = 0;
			dis[y - 1][x - 1] = 0;

		}
		
		prim();
		if (T)
		cout << endl;
	}
	return 0;
}


ZOJ 2048 highways

编辑推荐
1 2048
技术: -HTML -CSS -Javascript -JQuery 下面是代码内容 index.html 1 <!DOCTYPE html> 2 <
2 2048
最近2048非常热门,所以我用C#在移动端自己做了一个wp的2048来玩玩一下。 2048其实是一个很简单的小
总结——2048 第一次做成的小游戏 1.实现2048游戏界面,需要使用哪些组件? JButton JFrame FlowLay
这是我写的第一个小游戏,在windows下的Dev c++中用C语言来实现的,通过不断的清屏,打印,清屏,打
绿色2048 最近2048小游戏非常火。 做了一个,可以通过以下链接下载或通过附件下载,安装到android手
命令行2048 By 白熊花田(http://blog.csdn.net/whiterbear) 转载需注明出处,谢谢。 写了一个基于命
#include<iostream> #include<queue> #include <windows.h> #include <conio.
打包好的APK:http://pan.baidu.com/share/link?shareid=1088710780&uk=185595768 1.游戏画面布局: 2
  2048,一个最近风靡全球的游戏。   2048,一个令玩家爱不释手的游戏。   我认为,你玩转2048
自从JavaFX被纳入Java 8之后,JavaFX团队决定跳过几个版本,追赶Java 8。而如今的JavaFX的与以往的S
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号