Kruskal

70 分，超时。给边排序会很占用时间。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000;
const int MAXM = MAXN * (MAXN - 1) / 2;
struct Edge
{
    int u, v;
};
Edge e[MAXM + 5];
int n, m;
int x[MAXN + 5], y[MAXN + 5];
double dis(int i, int j)
{
    return sqrt((long long)(x[i] - x[j]) * (x[i] - x[j]) +
                (long long)(y[i] - y[j]) * (y[i] - y[j]));
}
bool cmp(Edge a, Edge b)
{
    return dis(a.u, a.v) < dis(b.u, b.v);
}
int fa[MAXN + 5];
int findFa(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    m = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            m++;
            e[m].u = i;
            e[m].v = j;
        }
    // 并查集初始化
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    // kruskal 算法
    sort(e + 1, e + m + 1, cmp);
    double sum = 0;
    for (int i = 1; i <= m; i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        double w = dis(u, v);
        int faU = findFa(u);
        int faV = findFa(v);
        if (faU != faV)
        {
            fa[faU] = faV;
            sum += w;
        }
    }
    cout << fixed << setprecision(2) << sum;
    return 0;
}

Prim $O(n^2)$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000;
int n, m;
int x[MAXN + 5], y[MAXN + 5];
vector<int> e[MAXN + 5];
// 到树的距离
double dis[MAXN + 5];
// 在不在树上
bool vis[MAXN + 5];
double len(int i, int j)
{
    return sqrt((long long)(x[i] - x[j]) * (x[i] - x[j]) +
                (long long)(y[i] - y[j]) * (y[i] - y[j]));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    // Prim
    for (int i = 1; i <= n; i++)
        dis[i] = 1e12, vis[i] = false;
    dis[1] = 0;
    double sum = 0; // 边之和、边的条数
    for (int i = 1; i <= n; i++)
    {
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!vis[i] && (u == -1 || dis[i] < dis[u]))
                u = i;
        // 这题必然有解，不用检查 u 是否合法
        vis[u] = true;
        sum += dis[u];
        for (int v = 1; v <= n; v++)
        {
            if (len(u, v) < dis[v])
                dis[v] = len(u, v);
        }
    }
    cout << fixed << setprecision(2) << sum;
    return 0;
}