游客 注册 | 登录
中文 | En

2035 - A MST Problem

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

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 .

输入/输出样例

输入格式

2
2
1 1 0
2 2 0
3
1 2 3
0 0 0
1 1 1

输出格式

1.41
3.97

C++解答

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 35;

double x[N], y[N], z[N];
int father[N];

struct node{
    int u, v;
    double d;
    bool operator < (const struct node n) const {
        return d < n.d;
    }
}e[500];

double DIS( int a, int b ) {
    return sqrt( (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])+(z[a]-z[b])*(z[a]-z[b]) );
}

int find( int x ) {
    if( father[x] == x ) return father[x];
    return ( father[x] = find( father[x] ) );
}

int main()
{
    int t, n, m, i, j, c;
    double ans;
    cin>>t;
    while(t--) {
        cin>>n;
        for( i = 0; i < n; ++i )
            father[i] = i,
            cin>>x[i]>>y[i]>>z[i];
        for( ans = c = m = i = 0; i < n; ++i )
            for( j = i + 1; j < n; ++j )
                e[m].u = i, e[m].v = j, e[m++].d = DIS(i,j);
        sort( e, e + m );
        for( i = 0; i < m; ++i ) {
            //cout<<e[i].d<<endl;
            int u = find(e[i].u);
            int v = find(e[i].v);
            if( u != v ) {
                ans += e[i].d;
                c++;
                father[u] = v;
            }
            if( c == n - 1 ) break;
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}
请先登陆