题目大意:本题是中文题，可以直接在OJ上看
解题思路:最小生成树
1)本题的关键在于把二维的点转化成一维的点
for (i = 0; i < n; ++i) {
scanf("%d%d", &point[i].x, &point[i].y);
point[i].id = i;
}
2)可用边的计算
int count = 0;
for (i = 0; i < n; ++i) {
for (j = i + 1; j < n; ++j) {
double distances = getDistance(point[i],point[j]); if (distances >= 10.0 && distances <= 1000.0) {
e[count].begin = point[i].id;
e[count].end = point[j].id;
e[count].weight = distances;
count++;
}
}
}
代码如下:
/*
* 1875_3.cpp
*
* Created on: 2013年8月26日
* Author: Administrator
*/ #include <iostream>
#include <math.h>
using namespace std; struct edge {
int begin;
int end;
double weight;
}; struct Point {
int x;
int y;
int id;
}; const int maxn = 6000;
int father[maxn];
edge e[maxn]; int find(int a) {
if (a == father[a]) {
return a;
} father[a] = find(father[a]);
return father[a];
} double kruscal(int count) {
int i;
double sum = 0;
for (i = 0; i < maxn; ++i) {
father[i] = i;
} for (i = 0; i < count; ++i) {
int fx = find(e[i].begin);
int fy = find(e[i].end); if (fx != fy) {
father[fx] = fy;
sum += e[i].weight;
}
}
return sum;
} bool compare(const edge& a, const edge& b) {
return a.weight < b.weight;
} double getDistance(const Point& a, const Point& b) {
return sqrt(
(double) ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
} int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int i, j;
memset(father, 0, sizeof(father));
for (i = 0; i < n; ++i) {
e[i].begin = -1;
e[i].end = -1;
e[i].weight = 0;
}
Point point[n + 1]; for (i = 0; i < n; ++i) {
scanf("%d%d", &point[i].x, &point[i].y);
point[i].id = i;
} int count = 0;
for (i = 0; i < n; ++i) {
for (j = i + 1; j < n; ++j) {
double distances = getDistance(point[i],point[j]); if (distances >= 10.0 && distances <= 1000.0) {
e[count].begin = point[i].id;
e[count].end = point[j].id;
e[count].weight = distances;
count++;
}
}
} sort(e,e + count,compare);
double result = kruscal(count); int num = 0;
for (i = 0; i < n; ++i) {
if (father[i] == i) {
num++;
}
} if (num == 1) {
printf("%.1lf\n", result * 100);
} else {
printf("oh!\n");
}
}
}