村庄建设
题目概述
补题链接
方法和代码
最小生成树，但是要自己构边，可以用prime，也可以用kruskra，这里用kruskra来写。
/*
Code by lifehappy 2020:04:19
方法：Kruskra最小生成树
*/
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int N = 1e6 + 10;
int sgn(double x) {
if(fabs(x) < eps) return 0;
if(x > 0) return 1;
return -1;
}
struct point {
double x, y, z;
point(double a = 0.0, double b = 0.0, double c = 0.0) : x(a), y(b), z(c) {}
point operator - (point t) {
return point(x - t.x, y - t.y, z - t.z);
}
}p[N];
double dis(point a, point b) {
a = a - b;
return sqrt(a.x * a.x + a.y * a.y) + a.z * a.z;
}
struct Edge {
int x, y;
double dis;
bool operator < (Edge t) {
return (sgn(dis - t.dis) <= 0);
}
}a[N];
int n, cnt, fa[N], sum;
void init() {
for(int i = 0; i < n; i++)
fa[i] = i;
}
int find(int rt) {
return rt == fa[rt] ? rt : fa[rt] = find(fa[rt]);
}
int main() {
// freopen("in.txt", "r", stdin);
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%lf %lf %lf", &p[i].x, &p[i].y, &p[i].z);
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
a[cnt].x = i, a[cnt].y = j;
a[cnt].dis = dis(p[i], p[j]);
cnt++;
}
}
init();
double ans = 0;
sort(a, a + cnt);
for(int i = 0; i < cnt; i++) {
int fx = find(a[i].x);
int fy = find(a[i].y);
if(fx != fy) {
fa[fx] = fy;
ans += a[i].dis;
sum++;
}
if(sum + 1 == n) break;
}
printf("%.2f
", ans);
return 0;
}
郊外植树
题目概述
补题链接
方法和代码
贪心的思想，优先栽植半径大的数。
/*
Code by lifehappy 2020:04:19
方法：贪心
*/
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int N = 50;
int sgn(double x) {
if(fabs(x) < eps) return 0;
if(x > 0) return 1;
return -1;
}
struct point {
double x, y, r;
point(double a = 0.0, double b = 0.0, double c = 0.0) : x(a), y(b), r(c) {}
point operator - (point t) {
return point(x - t.x, y - t.y, r - t.r);
}
bool operator < (point t) {
return (sgn(r - t.r) >= 0);
}
}a[N], b[N];
double dis(point a, point b) {
a = a - b;
return sqrt(a.x * a.x + a.y * a.y);
}
int n;
int main() {
// freopen("in.txt", "r", stdin);
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i].x >> a[i].y >> a[i].r;
sort(a, a + n);
int ans = 0, pos = 0;
for(int i = 0; i < n; i++) {
int flag = 1;
for(int j = 0; j < pos; j++) {
double d = dis(a[i], b[j]);
if(sgn(d - a[i].r - b[j].r) == -1) {
flag = 0;
break;
}
}
if(flag) {
ans += a[i].r * a[i].r;
b[pos++] = a[i];
}
}
cout << ans << endl;
return 0;
}