复习版
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define not !
#define and &&
#define or ||
#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)
#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, ~0) printf("%d%c", getbit(x, i), i ? 9 : 10); }
#define SWAP(a, b) { typeof(a) tmp = a; a = b; b = tmp; }
typedef long long int ll;
#define r() fast_read()
bool is_digit(const char c) {
return c >= 48 and c <= 57;
}
ll my_pow(int base, int exponent) {
return exponent ? my_pow(base, exponent - 1) * base : 1;
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (not is_digit(c)) {
if (c == '-') sign = ~0;
c = getchar();
}
while (is_digit(c)) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
typedef struct {
int* parents;
int count;
} UF;
void InitUF(UF* uf, int count, const size_t len) {
uf->parents = malloc(len * sizeof(int));
for (int i = 0; i < len; ++i) uf->parents[i] = i;
uf->count = count;
}
int Find(UF* uf, int x) {
if (uf->parents[x] ^ x)
uf->parents[x] = Find(uf, uf->parents[x]);
return uf->parents[x];
}
int Unite(UF* uf, int u, int v) {
u = Find(uf, u), v = Find(uf, v);
if (u == v) return 0;
uf->parents[u] = v;
--uf->count;
return 1;
}
int IsConnected(UF* uf, int u, int v) {
return Find(uf, u) == Find(uf, v);
}
void DestroyUF(UF* uf) {
free(uf->parents);
}
#define MAX_N 110
int edge_cnt;
typedef struct Edge Edge;
struct Edge {
int u, v;
double w;
} edges[MAX_N * MAX_N];
int cmp_edge(const void* a, const void* b) {
double diff = ((Edge*) a)->w - ((Edge*) b)->w;
return diff ? diff > 0 ? 1 : -1 : 0;
}
typedef struct Coordinate Coord;
struct Coordinate {
int x, y;
} coords[MAX_N];
double distance(const Coord* a, const Coord* b) {
return sqrt((a->x - b->x) * (a->x - b->x) + (a->y - b->y) * (a->y - b->y));
}
int t, n;
// Kruskal一般指克鲁斯卡尔算法
void kruskal(const int n) {
qsort(edges, edge_cnt, sizeof(Edge), cmp_edge);
UF uf;
InitUF(&uf, n, MAX_N);
int u, v, cnt = 0;
double w, ans = 0;
rep(e, 0, edge_cnt) {
u = edges[e].u, v = edges[e].v, w = edges[e].w;
if (not Unite(&uf, u, v)) continue;
ans += w;
if (++cnt == n - 1) {
printf("%.1lf\n", ans * 100);
DestroyUF(&uf);
return;
}
}
puts("oh!");
DestroyUF(&uf);
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
t = r();
while (t--) {
n = r();
rep(i, 0, n)
(coords + i)->x = r(), (coords + i)->y = r();
edge_cnt = 0; // init
rep(i, 0, n) rep(j, i + 1, n) {
const double d = distance(coords + i, coords + j);
if (d < 10 or d > 1000) continue;
edges[edge_cnt++] = (Edge) {i, j, d};
}
if (edge_cnt < n - 1) {
puts("oh!");
continue;
}
kruskal(n);
}
// fclose(stdin);
return ~~(0 ^ 0);
}
Kruskal
#include <iostream>
#include <cmath>
#include <algorithm>
#define r() fast_read()
#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)
using namespace std;
using ll = long long int;
const int N = 1E2 + 1E1;
inline ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (c < 48 or c > 57) {
if (c == '-') sign = ~0;
c = getchar();
}
while (c >= 48 and c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
int edge_cnt;
struct Edge {
int u, v;
double w;
bool operator<(const Edge& o) const {
return w < o.w;
}
} edges[N * N];
struct Point {
int x, y;
double distance(const Point& o) const {
return sqrt((x - o.x) * (x - o.x) + (y - o.y) * (y - o.y));
}
} points[N];
struct UF {
public:
UF() { f(i, 0, N) p_[i] = i; }
int find(int x) {
if (p_[x] ^ x) p_[x] = find(p_[x]);
return p_[x];
}
bool unite(int p, int q) {
int root_p = find(p), root_q = find(q);
if (root_p == root_q) return false;
p_[root_p] = root_q;
return true;
}
private:
int p_[N];
};
int t, c;
inline double kruskal(void) {
sort(edges, edges + edge_cnt);
UF uf;
double ans = 0.0; int cnt = 0;
f(e, 0, edge_cnt) {
int u = edges[e].u, v = edges[e].v;
double w = edges[e].w;
if (not uf.unite(u, v)) continue;
ans += w;
if (++cnt == c - 1) return ans * 100.0;
}
return -1;
}
int main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
t = r();
while (t--) {
c = r();
f(i, 0, c) points[i].x = r(), points[i].y = r();
edge_cnt = 0;
f(i, 0, c) f(j, i + 1, c) {
double d = points[i].distance(points[j]);
if (d >= 10 and d <= 1000) edges[edge_cnt++] = {int(i), int(j), d};
}
double ans = kruskal();
if (ans == -1) puts("oh!");
else printf("%.1lf\n", ans);
}
// fclose(stdin);
return 0;
}