建立最小生成樹(Minimum Spanning Tree, MST)並算出樹上之權重(也就是兩點之間的距離)的總和即可得解。
C++(0.009)
/*******************************************************/ /* UVa 10034 Freckles */ /* Author: LanyiKnight [at] knightzone.org */ /* Version: 2015/03/15 */ /*******************************************************/ #include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> using namespace std; struct Point{ int group; double x; double y; }; struct Line{ int aPointIndex, bPointIndex; double length; }; bool compareByLength(const Line &a, const Line &b){ return a.length < b.length; } double pointDistance(const Point &a, const Point &b){ double deltaX = a.x - b.x, deltaY = a.y - b.y; return sqrt(deltaX * deltaX + deltaY * deltaY); } bool isBuildMSTFinished(const Point points[], int n){ for( int i = 0 ; i < n-1 ; ++i ){ if( points[i].group != points[i+1].group ){ return false; } } return true; } void putInSameGroup(Point points[], int n, int group1, int group2){ int minGroup = min(group1, group2); for( int i = 0 ; i < n ; ++i ){ if( points[i].group == group1 || points[i].group == group2 ){ points[i].group = minGroup; } } } int main(){ int testcase; while( scanf("%d", &testcase) != EOF ){ for( int caseCount = 0 ; caseCount < testcase ; ++caseCount ){ if( caseCount > 0 ) printf("\n"); int n; scanf("%d", &n); Point points[105]; for( int i = 0 ; i < n ; ++i ){ scanf("%lf%lf", &(points[i].x), &(points[i].y)); points[i].group = i; } vector<Line> lines; for( int i = 0 ; i < n ; ++i ){ for( int j = i + 1 ; j < n ; ++j ){ Line l; l.aPointIndex = i; l.bPointIndex = j; l.length = pointDistance(points[i],points[j]); lines.push_back(l); } } sort( lines.begin(), lines.end(), compareByLength); double pathLengthSum = 0; for( int i = 0 ; !isBuildMSTFinished(points, n) ; ++i ){ if( points[lines[i].aPointIndex].group == points[lines[i].bPointIndex].group ){ continue; } pathLengthSum += lines[i].length; putInSameGroup(points, n, points[lines[i].aPointIndex].group, points[lines[i].bPointIndex].group); } printf("%.2lf\n", pathLengthSum); } } return 0; }