2008浙大研究生复试热身赛（2）——全真模拟题目链接：?pid=1875题目大意：中文题，如题题目分析：其实本来是个很简单的MST，可是给的是坐标，，用Kruskal时要将每个点区分开，这里用hash的思想，因为坐标最大为1000，就给每个点设一个id ＝ x*1000 + y，合并的时候注意题目要求距离要在10-1000之间，这里还要用并查集判下连通性，我没判的居然也能过，后来才意识到#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;int const INF = 0xffffff;int const MAX = 6000;int n, cnt;double ans;int fa[1002000], rank[1002000];struct Node{int u, v, id;}nd[105];struct Edge{Node x, y;double val;}e[MAX];bool cmp(Edge a, Edge b){return a.val < b.val;}double dist(int x1, int y1, int x2, int y2){return sqrt((x1 – x2) * (x1 – x2) + (y1 – y2) * (y1 – y2));}void UFset(){for(int i = 0; i < 1002000; i++)fa[i] = i;memset(rank, 0, sizeof(rank));}int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}void Union(int a, int b){int r1 = Find(a);int r2 = Find(b);if(r1 == r2)return;if(rank[r1] > rank[r2])fa[r2] = r1;else{fa[r1] = r2;if(rank[r1] == rank[r2])rank[r1]++;}}bool Kruskal(){int u, v;int num = 0;UFset();for(int i = 0; i < cnt; i++){u = e[i].x.id;v = e[i].y.id;double tmp = dist(e[i].x.u, e[i].x.v, e[i].y.u, e[i].y.v);if(tmp >= 10 && tmp <= 1000){if(Find(u) != Find(v)){ans += (e[i].val * 100);Union(u, v);num++;}if(num == n – 1)return true;}}return false;}int main(){int T;scanf("%d", &T);while(T–){int x, y;cnt = 0;ans = 0;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d %d", &nd[i].u, &nd[i].v);nd[i].id = nd[i].u * 1000 + nd[i].v;}for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){e[cnt].x.u = nd[i].u;e[cnt].x.v = nd[i].v;e[cnt].x.id = nd[i].id;e[cnt].y.u = nd[j].u;e[cnt].y.v = nd[j].v;e[cnt].y.id = nd[j].id;e[cnt++].val = dist(nd[i].u, nd[i].v, nd[j].u, nd[j].v);}}sort(e, e + cnt, cmp);if(!Kruskal())printf("oh!\n");elseprintf("%.1f\n", ans);}}
坐在外婆的沙滩，看最白的帆影。
