这是一道最小生成树的题目
实际上，那些条件都是唬人的，根本没用。
对于条件（2）：不妨假设A申请修建公路AB，B申请修建公路BC，C申请修建公路CA，构成了环。
然而，A申请AB，则有AB<AC
B申请BC，则有BC<BA
C申请CA，则有CA<CB
所以AB<AC<CB<AB 矛盾了
从而可得：对于一个图来说，节点的最短边不可能成环。
所以这题是裸最小生成树。
***************************************
然而问题并没有解决，
这道题有非常恶心的卡时。
首先是稠密图，5000*5000的边会炸空间，所以不能用kru
即使是prim，也不能用堆优化（复杂度会引入很大的E），老老实实的朴素n平方算法。
所以对于稠密图，有时候还不如不用堆。
对于边，直接计算即可了，不必存贮。
还有计算距离的时候记得把int转化成double。
**************************************
附代码：
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #define MAXV 5005 #define INF 0x7fffffff using namespace std; int V; pair<int,int> P[MAXV]; double lenth(int x,int y){ return sqrt((double)(P[x].first-P[y].first)*(P[x].first-P[y].first)+(double)(P[x].second-P[y].second)*(P[x].second-P[y].second)); } double prim(){ double ret=0; double mincost[MAXV]; bool b[MAXV]={0}; for(int i=1;i<=V;i++){ mincost[i]=lenth(1,i); } while(1){ int v=0; for(int i=1;i<=V;i++){ if(!b[i]&&(!v||mincost[i]<mincost[v])){ v=i; } } if(v==0){ break; } b[v]=1; ret+=mincost[v]; for(int i=1;i<=V;i++){ mincost[i]=min(mincost[i],lenth(v,i)); } } return ret; } int main() { scanf("%d",&V); for(int i=1;i<=V;i++){ scanf("%d%d",&P[i].first,&P[i].second); } printf("%.2f",prim()); return 0; }
