Freckles

分析：在坐标点构成的图上应用最小生成树算法即可。注意几点：

1）边权是动态计算出来的

2）每对坐标之间都可以有一条边

3）由于图的顶点不再由整数标识，因此用map代替典型算法中的vector

<!--more-->

#include <iostream>
#include <vector>
#include <map>
#include <limits>
#include <cmath>
#include <cstdio>

using namespace std;

class Point {
public:
  Point() : x(0), y(0) {}

  Point(double ax, double ay) : x(ax), y(ay) {}

  bool operator <(const Point & p) const {
    bool r;
    if (x < p.x)
      r = true;
    else if (x > p.x)
      r = false;
    else {
      if (y < p.y)
        r = true;
      else
        r = false;
    }
    return r;
  }

  double distance(const Point & p) const {
    double dx = x - p.x;
    double dy = y - p.y;
    return sqrt(dx * dx + dy * dy);
  }

  double x;
  double y;
};

typedef vector<Point> Graph;

double mst(const Graph & g) {
  double r = 0;
  map<Point, bool> intree;
  map<Point, double> dist;
  map<Point, Point> pred;
  for (int i = 0; i < g.size(); i++) {
    dist[g[i]] = numeric_limits<double>::max();
  }
  const Point * p = &g[0];
  while (p) {
    intree[*p] = true;
    const Point * np = 0;
    double min = numeric_limits<double>::max();
    map<Point, double>::iterator it = dist.begin();
    for (; it != dist.end(); it++) {
      const Point & p2 = it->first;
      //use find to avoid adding p2 to intree if not yet
      if (intree.find(p2) == intree.end()) {
        double d = p->distance(p2);
        if (d < it->second) {
          it->second = d;
          pred[p2] = *p;
        }
        if (it->second < min) {
          min = it->second;
          np = &p2; //It doesn't matter np(then passed to p) points to inside of dist rather than g
        }
      }
    }
    p = np;
  }
  map<Point, Point>::iterator it = pred.begin();
  for (; it != pred.end(); it++) {
    r += it->first.distance(it->second);
  }
  return r;
}

int main() {
  int n = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    Graph g;
    int nv = 0;
    cin >> nv;
    for (int j = 0; j < nv; j++) {
      double x, y;
      cin >> x >> y;
      g.push_back(Point(x, y));
    }
    if (i) {
      printf("n");
    }
    printf("%0.2fn", mst(g));
  }
  return 0;
}