kruskal MLE求助喵~
查看原帖
kruskal MLE求助喵~
1038998
Franklin_Tse楼主2023/11/28 09:44

#2#8#9#10MLE,别的过了

#include <bits/stdc++.h>
#define int long long

using namespace std;
using ll = long long;

const int N = 5e3 + 5;

struct node
{
    int u, v;
    double w;
    bool operator < (const node &m)const
    {
        if(w != m.w)return w < m.w;
        if(u != m.u)return u < m.u;
        return v < m.v;
    }
};

vector<node> g;

int a[N], b[N];

int pre[N];
int root(int x){return pre[x] = (pre[x] == x ? x : root(pre[x]));}

void solve()
{
    int n;cin >> n;
    for(int i = 1; i <= n; ++ i)pre[i] = i;
    for(int i = 1; i <= n; ++ i)cin >> a[i] >> b[i];
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= n; ++ j)
        {
            if(i == j)continue;
            double w = sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));
            g.push_back({i, j, w});
        }
    
    sort(g.begin(), g.end());

    double ans = 0;
    for(const auto &[u, v, w] : g)
    {
        if(root(u) == root(v))continue;

        pre[root(u)] = root(v);
        ans += w;
    }
    cout << fixed << setprecision(2) << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    while(_ --)solve();
    return 0;
}

2023/11/28 09:44
加载中...