本想着做完这道题，就暂时告别MST，但越到了这个时候，惊喜也就越多，呵呵。
题目链接：https://www.luogu.org/problemnew/show/P1265
哎，上去就mengbi第二个规则，自己试了好半天，始终举不出例子来，只好去看题解，，，真想吐血！原来第二种情况根本不存在，每个城市都向离自己最近的城市修公路，怎么会出现环呢？这道题其实也是要求最小生成树！
好，Kruskal上！砰!
n<=5000？那么边数最多可有25000000！显然内存方面就会炸。
再仔细一看题解，哦，是用Prim。记得曾经dalao和我说过，Prim并不是一无是处，他就用到过一次，当时没仔细听，没想到最终还是翻了船。
去啃Prim，发现确实Kruskal不能完全代替他。具体详见另一篇博客《Prim算法》。
仔细想想，其实题目的描述就是Prim算法的过程，每次找一个和已加入最小生成树的点距离最近的点加入最小生成树。
边是不可以全部保存的，而Prim算法的过程刚好可以不用保存每条边，只需动态查询边的长度即可。Prim适用于稠密图，所以这道题非Prim莫属了。
高高兴兴写上Prim提交。。。什么！只有10分？找了好半天都不知道哪错了，摁着正解使劲读，最后才意识到求两点间距离时原来会溢出。
比如：sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))，万一坐标的范围很大，中间过程（像(x1-x2)*(x1-x2)）就会溢出！
唔，可算是完了。
1 #include <cstdio> 2 #include <cmath> 3 #include <queue> 4 5 using namespace std; 6 7 const int maxn = 5005; 8 const double inf = 1e16; 9 10 int x[maxn], y[maxn], vis[maxn]; 11 double dist[maxn]; 12 13 inline long long pw2(int x) { 14 return 1LL * x * x; 15 } 16 17 inline double dis(int i, int j) { 18 return sqrt(pw2(x[i] - x[j]) + pw2(y[i] - y[j])); 19 } 20 21 struct node { 22 int id; 23 double dist; 24 node(int i, double d) : id(i), dist(d) {} 25 bool operator < (const node& rhs) const { 26 return dist > rhs.dist; 27 } 28 }; 29 30 priority_queue<node> q; 31 32 int main() { 33 int n; 34 scanf("%d", &n); 35 for (int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]); 36 double ans = 0; 37 for (int i = 2; i <= n; ++i) dist[i] = inf; 38 q.push(node(1, 0)); 39 while (!q.empty()) { 40 int u = q.top().id; 41 q.pop(); 42 if (vis[u]) continue; 43 vis[u] = 1; 44 ans += dist[u]; 45 for (int v = 1; v <= n; ++v) { 46 if (v == u) continue; 47 if (dist[v] > dis(u, v)) { 48 dist[v] = dis(u, v); 49 q.push(node(v, dist[v])); 50 } 51 } 52 } 53 printf("%.2f", ans); 54 return 0; 55 }