1012: A MST Problem

时间限制: 1 Sec 内存限制: 32 MB
提交: 63 解决: 33
[提交][状态][讨论版][命题人:外部导入]

题目描述

It is just a mining spanning tree ( 最小生成树 ) problem, what makes you a little difficult is that you are in a 3D space.

输入

The first line of the input contains the number of test cases in the file. And t he first line of each case

contains one integer numbers n(0<n<30) specifying the number of the point . The n next n line s, each line

contain s Three Integer Numbers xi,yi and zi, indicating the position of point i.

输出

For each test case, output a line with the answer, which should accurately rounded to two decimals .

样例输入

样例输出

1.41

3.97

#include<iostream>

#include<cmath>

#include<cstdio>

#define INF 99999999

#define MAXV 100

using namespace std;

typedef struct

{

	double edges[100][100];

	int n;

	int e;

}MatGraph;

struct point

{

	int x;

	int y;

	int z;

}point[100];

MatGraph g;

void CreateMat(MatGraph &g, double graph[100][100], int n)

{

	int i, j;

	g.n = n;

	for(i = 0; i < g.n; ++i)

	{

		for(j = 0; j < g.n; ++j)

		{

			g.edges[i][j] = graph[i][j];

		}

	}

}

double Prim(MatGraph g, int v)

{

	double lowcost[100];

	double min_ = INF;

	double r = 0;

	int i, j, k;

	int n = g.n;

	for(i = 0; i < n; ++i)

	{

		lowcost[i] = g.edges[v][i];

	}

	for(i = 1; i < n; ++i)

	{

		min_ = INF;

		for(j = 0; j < n; ++j)

		{

			if(lowcost[j] != -1 && lowcost[j] < min_)

			{

				min_ = lowcost[j];

				k = j;

			}

		}

		lowcost[k] = -1;

		r = r + min_;

		for(j = 0; j < n; ++j)

		{

			if(g.edges[k][j] < lowcost[j] && g.edges[k][j] != -1)

			{

				lowcost[j] = g.edges[k][j];

			}

		}

	}

	return r;

}

int main()

{

	double length, ans, result;

	double graph[100][100];

	int num, i, j, k, l, t, n;

	cin >> t;

	while(t--)

	{

		cin >> n;

		for(i = 0; i < n; ++i)

		{

			for(j = 0; j < n; ++j)

			{

				graph[i][j] = INF;

			}

		}

		for(i = 0; i < n; ++i)

		{

			cin >> point[i].x >> point[i].y >> point[i].z;

		}

		for(i = 0; i < n; ++i)

		{

			for(j = 0; j < n; ++j)

			{

				length = sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y) + (point[i].z - point[j].z)*(point[i].z - point[j].z));

				graph[i][j] = graph[j][i] = length;

			}

		}

		for(i = 0; i < n; ++i)

		{

			for(j = 0; j < n; ++j)

			{

				if(i == j)

				{

					graph[i][j] = -1;

				}

			}

		}

		CreateMat(g, graph, n);

		result = Prim(g, 0);

		printf("%.2lf\n", result);

	}

	return 0;

}

巴特西

1012: A MST Problem