Freckles

http://acm.pku.edu.cn/JudgeOnline/problem?id=2560

Description

In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through.
Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.

Input

The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.

Output

Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.

Source

Waterloo local 2000.09.23


Solving

주근깨의 좌표가 주어진다. 모든 주근깨를 하나로 연결하기 위해 선을 그을때 그어야 하는 모든 선의 최소길이를 구하여라

최소신장트리(Minimum Spanning Tree)문제이다.
MST는 쿠르스칼이나 프림스의 알고리즘을 이용하여 풀면 된다.
#include <cstdlib> #include <vector> #include <cmath> #include <algorithm> using namespace std; template<class T> inline T MAX(const T& a, const T& b) {return (a>=b)?a:b;} template<class T> inline T MIN(const T& a, const T& b) {return (a<=b)?a:b;} // Graph struct Edge { int a; int b; double w; }; int EdgeGreat(Edge a, Edge b) {return a.w < b.w;} // 인접행렬 G -> Edge리스트(가중치가 작은순으로 정렬) vector<Edge> MakeEdgeFromGraph(vector<vector<double> > G, bool bidrection) { int n = G.size(); int i, j; vector<Edge> E; for (i = 0; i < n; i++) { int start = 0; if (bidrection == true) start = i+1; for (j = start; j < n; j++) { if (G[i][j] != -1) { Edge e = {i, j, G[i][j]}; E.push_back(e); } } } sort(E.begin(), E.end(), EdgeGreat); return E; } vector<Edge> Kruskal(vector<vector<double> > G) { int n = G.size(); int i, j; vector<Edge> E; vector<Edge> MinSpanEdge; E = MakeEdgeFromGraph(G, true); vector<int> graphSet(n, 0); for (i = 0; i < n; i++) graphSet[i] = i; for (i = 0; i < E.size(); i++) { int a = E[i].a; int b = E[i].b; while (graphSet[a] != a) a = graphSet[a]; while (graphSet[b] != b) b = graphSet[b]; graphSet[a] = graphSet[b] = MIN(graphSet[a], graphSet[b]); graphSet[E[i].a] = graphSet[E[i].b] = MIN(graphSet[a], graphSet[b]); if (a != b) { Edge e = {E[i].a, E[i].b, E[i].w}; MinSpanEdge.push_back(e); if (MinSpanEdge.size() == n-1) break; } } if (MinSpanEdge.size() != n-1) MinSpanEdge.clear(); return MinSpanEdge; } int main() { int n; while (scanf("%d", &n) > 0) { int i, j; vector<vector<double> > G; for (i = 0; i < n; i++) { vector<double> g(n,-1); G.push_back(g); } vector<double> x(n); vector<double> y(n); for (i = 0; i < n; i++) scanf("%lf%lf", &x[i], &y[i]); for (i = 0; i < n; i++) { for (j = i+1; j < n; j++) { G[i][j] = G[j][i] = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j])); } } vector<Edge> edge = Kruskal(G); double ans = 0; for (i = 0; i < edge.size(); i++) { ans += edge[i].w; } printf("%.2lf\n", ans); } }