- 浇地
1
- @ 2026-7-20 11:07:36
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct DSU {
vector<int> f;
DSU(int n) {
f.assign(n + 1, 0);
for (int i = 1; i <= n; i++) f[i] = i;
}
int rt(int u) {
if (u == f[u]) return u;
return f[u] = rt(f[u]);
}
int same(int u, int v) {
return rt(u) == rt(v);
}
void merge(int u, int v) {
f[rt(u)] = rt(v);
}
};
void solve() {
int n, c;
cin >> n >> c;
vector<array<int, 3>> e;
vector<int> x(n + 1), y(n + 1);
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
for (int j = 1; j < i; j++) {
int w = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
if (w >= c) {
e.push_back({w, i, j});
}
}
}
sort(e.begin(), e.end());
DSU dsu(n);
int sum = 0, cnt = 0;
for (auto [w, u, v] : e) {
if (dsu.same(u, v)) continue;
dsu.merge(u, v);
sum += w;
cnt++;
}
if (cnt == n - 1) {
cout << sum << '\n';
} else {
cout << "-1\n";
}
}
signed main() {
int t = 1;
// cin >> t;
while (t--) solve();
}
/*
g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt
*/
0 条评论
目前还没有评论...
信息
- ID
- 489
- 时间
- ms
- 内存
- MiB
- 难度
- 3
- 标签
- 递交数
- 178
- 已通过
- 44
- 上传者