2035 - A MST Problem
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; }