[BZOJ1626][Usaco2007 Dec]Building Roads 修建道路

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,000；0 <= Y_i <= 1,000,000)，兩個農場間道路的長度自然就是代表它們的點之間的距離。現在Farmer John也告訴了你農場間原有的M(1 <= M <= 1,000)條路分別連接了哪兩個農場，他希望你計算一下，為了使得所有農場連通，他所需建造道路的最小總長是多少。

Input

* 第1行: 2個用空格隔開的整數：N 和 M

?* 第2..N+1行: 第i+1行為2個用空格隔開的整數：X_i、Y_i * 第N+2..N+M+2行: 每行用2個以空格隔開的整數i、j描述了一條已有的道路， 這條道路連接了農場i和農場j

Output

* 第1行: 輸出使所有農場連通所需建設道路的最小總長，保留2位小數，不必做 任何額外的取整操作。為了避免精度誤差，計算農場間距離及答案時 請使用64位實型變量

Sample Input

4 1
1 1
3 1
2 3
4 3
1 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;
}

?