题目传送门 https://www.luogu.org/problemnew/show/P1265
这道题是稠密图, 要用 $Prim$, 可以对照 P1991 https://www.cnblogs.com/ac-evil/p/10325200.html 的 $Kruskal$, 但在这里用会 $MLE$ 会 $TLE$.
- #include <bits/stdc++.h>
- using namespace std;
- #define re register
- #define rep(i, a, b) for (re int i = a; i <= b; ++i)
- #define repd(i, a, b) for (re int i = a; i>= b; --i)
- #define maxx(a, b) a = max(a, b);
- #define minn(a, b) a = min(a, b);
- #define LL long long
- #define INF (1 << 30)
- inline int read() {
- int w = 0, f = 1; char c = getchar();
- while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
- while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();
- return w * f;
- }
- const int maxn = 5000 + 5;
- LL sqr(LL x) { return x * x; }
- double dist(int x1, int y1, int x2, int y2) { return sqrt(sqr(x1-x2) + sqr(y1-y2)); }
- int n, x[maxn], y[maxn], v[maxn];
- double ans = 0, t[maxn];
- int main() {
- n = read();
- rep(i, 1, n) x[i] = read(), y[i] = read();
- memset(v, 0, sizeof(v));
- int p = 1;
- v[p] = 1;
- rep(i, 1, n) t[i] = INF;
- rep(kase, 1, n-1) {
- int _min = 0;
- rep(i, 1, n)
- if (!v[i]) {
- minn(t[i], dist(x[p], y[p], x[i], y[i]));
- if (!_min || t[i] < t[_min]) _min = i;
- }
- ans += t[_min];
- v[_min] = 1;
- p = _min;
- }
- printf("%.2lf", ans);
- return 0;
- }
[洛谷 P1265] 公路修建
来源: http://www.bubuko.com/infodetail-2935372.html