HDU - 1875 （最小生成树）

题目链接

思路：把每个顶点编号，点之间的距离>=10且<=100,给这个两个点之间建边。建完之后求求最小生成树（MST）

AC代码

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 110;
struct node{int u, v;double w;
}q[N*N];
int n, m, cnt;
int xx[N], yy[N], pre[N];
void init(){for(int i = 1; i <= n; i++){pre[i] = i;}cnt = 0;
}
int Find(int x){if(x != pre[x]) pre[x] = Find(pre[x]);return pre[x];
}
void join(int x, int y){int tx = Find(x);int ty = Find(y);if(tx != ty) pre[ty] = tx;
}
bool cmp(node a, node b){return a.w < b.w;
}
double Kru(){double ans = 0;sort(q, q + cnt, cmp);for(int  i = 0; i < cnt; i++){if(Find(q[i].u) != Find(q[i].v)){join(q[i].u, q[i].v);ans += q[i].w;}}return ans;
}
int main(){#ifdef ONLINE_JUDGE#elsefreopen("in.txt", "r", stdin);#endif //ONLINE_JUDGEint t;scanf("%d", &t);while(t--){scanf("%d", &n);init();for(int  i = 1; i <= n; i++){scanf("%d%d", &xx[i], &yy[i]);}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){int dis = (xx[i] - xx[j])*(xx[i] - xx[j])+(yy[i] - yy[j])*(yy[i] - yy[j]);if(dis >= 100.0 && dis <= 1000000.0) {q[cnt].u = i;q[cnt].v = j;q[cnt++].w = sqrt((double)dis);}}}double ans = Kru();int cnt1 = 0;for(int i = 2; i <= n; i++){if(pre[i] == i) cnt1++;}if(cnt1 > 1) printf("oh!\n");else  printf("%.1lf\n", ans*100.0);}return 0;
}