本想着做完这道题，就暂时告别MST，但越到了这个时候，惊喜也就越多，呵呵。
题目链接：https://www.luogu.org/problemnew/show/P1265
哎，上去就mengbi第二个规则，自己试了好半天，始终举不出例子来，只好去看题解，，，真想吐血！原来第二种情况根本不存在，这道题其实也是要求最小生成树！
好，Kruskal上！砰!
n<=5000？那么边数最多可有25000000！显然内存方面就会炸。
再仔细一看题解，哦，是用Prim。记得曾经dalao和我说过，Prim并不是一无是处，他就用到过一次，当时没仔细听，没想到最终还是翻了船。
去啃Prim，发现确实Kruskal不能完全代替他。具体详见另一篇博客《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 const int maxn=5005; 4 const double inf=1e9; 5 int n,x[maxn],y[maxn],vis[maxn]; 6 double minw[maxn],ans=0; 7 double dis(int i,int j) { 8 return sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j])); 9 } //一定要注意这里别溢出！！！ 10 int main() { 11 scanf("%d",&n); 12 for(int i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]); 13 int index; 14 double mmin; 15 for(int i=2;i<=n;++i) minw[i]=inf; 16 for(int i=1;i<=n;++i) { 17 mmin=inf; 18 for(int j=1;j<=n;++j) if(!vis[j]&&minw[j]<mmin) index=j,mmin=minw[j]; 19 vis[index]=1; 20 ans+=mmin; 21 for(int j=1;j<=n;++j) { 22 double d=dis(index,j); 23 if(!vis[j]&&d<minw[j]) minw[j]=d; 24 } 25 } 26 printf("%.2f",ans); 27 return 0; 28 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9575468.html
