个旧市哪里有做网站,同时优化几个网站,wordpress 搭建教育,理财网站建设1626: [Usaco2007 Dec]Building Roads 修建道路 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1730 Solved: 727 [Submit][Status][Discuss]Description Farmer John最近得到了一些新的农场#xff0c;他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达… 1626: [Usaco2007 Dec]Building Roads 修建道路 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1730 Solved: 727 [Submit][Status][Discuss] Description Farmer John最近得到了一些新的农场他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达也就是说从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场。有些农场之间原本就有道路相连。 所有N(1 N 1,000)个农场用1..N顺次编号在地图上都表示为坐标为(X_i, Y_i)的点(0 X_i 1,000,0000 Y_i 1,000,000)两个农场间道路的长度自然就是代表它们的点之间的距离。现在Farmer John也告诉了你农场间原有的M(1 M 1,000)条路分别连接了哪两个农场他希望你计算一下为了使得所有农场连通他所需建造道路的最小总长是多少。 Input * 第1行: 2个用空格隔开的整数N 和 M * 第2..N1行: 第i1行为2个用空格隔开的整数X_i、Y_i * 第N2..NM2行: 每行用2个以空格隔开的整数i、j描述了一条已有的道路 这条道路连接了农场i和农场j Output * 第1行: 输出使所有农场连通所需建设道路的最小总长保留2位小数不必做 任何额外的取整操作。为了避免精度误差计算农场间距离及答案时 请使用64位实型变量 Sample Input 4 11 13 12 34 31 4输入说明: FJ一共有4个坐标分别为(1,1)(3,1)(2,3)(4,3)的农场。农场1和农场4之间原本就有道路相连。 Sample Output 4.00输出说明: FJ选择在农场1和农场2间建一条长度为2.00的道路在农场3和农场4间建一条长度为2.00的道路。这样所建道路的总长为4.00并且这是所有方案中道路总长最小的一种。 已经有的边权值赋为0做最小生成树 #include cmath
#include cstdio
#include cstring
#include algorithm
using namespace std;
char buf[10000000], *ptr buf - 1;
inline int readint(){int n 0;char ch *ptr;while(ch 0 || ch 9) ch *ptr;while(ch 9 ch 0){n (n 1) (n 3) ch - 0;ch *ptr;}return n;
}
typedef long long ll;
const int maxn 1000 10, maxm 500000 1000 10;
struct Edge{int u, v;double w;Edge(){}Edge(int _u, int _v, double _w): u(_u), v(_v), w(_w){}bool operator (const Edge x) const {return w x.w;}
}e[maxm];
int cnt 0;
inline void add(int u, int v, double w){e[cnt] Edge(u, v, w);
}
inline ll sqr(int x){return (ll)x * x;
}
int x[maxn], y[maxn];
inline double dis(int a, int b){return sqrt(sqr(x[a] - x[b]) sqr(y[a] - y[b]));
}
int fa[maxn];
int Find(int a){return a fa[a] ? a : fa[a] Find(fa[a]);
}
int main(){fread(buf, sizeof(char), sizeof(buf), stdin);int n, m;n readint();m readint();for(int i 1; i n; i){x[i] readint();y[i] readint();}for(int i 1; i n; i)for(int j 1; j i; j)add(i, j, dis(i, j));for(int u, v, i 1; i m; i){u readint();v readint();add(u, v, 0);}sort(e 1, e cnt 1);for(int i 1; i n; i) fa[i] i; double ans 0.0;for(int i 1, k 0; i cnt k n - 1; i){if(Find(e[i].v) Find(e[i].u)) continue;fa[Find(e[i].v)] Find(e[i].u);k;ans e[i].w;}printf(%.2lf\n, ans);return 0;
} 转载于:https://www.cnblogs.com/ruoruoruo/p/7481884.html
