求助~~ 只过了样例
查看原帖
求助~~ 只过了样例
792020
Bad_guy楼主2023/9/5 22:33
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N = 1010;
ll s;
ll n, m;
ll p[N];
struct E
{
    ll x, y;
} e[N];
struct Edge
{
    ll a, b;
    double w;
    bool operator < (const Edge &W) const 
    {
        return w < W.w;
    }
} edges[N];
ll find(ll x)
{
    if(x != p[x])
        p[x] = find(p[x]);
    return p[x];
}
double kruskal()
{
    sort(edges, edges + s);
    for (ll i = 1; i <= n; i++)
        p[i] = i;
    double res = 0.0;
    for (ll i = 0; i < s; i++)
    {
        ll a = edges[i].a, b = edges[i].b;
        double w = edges[i].w;
        a = find(a), b = find(b);
        if(a != b)
        {
            p[a] = b;
            res += w;
        }
    }
    return res;
}
double gap(ll x, ll y)
{
    return (double)(sqrt((double)(e[x].x - e[y].x) * (e[x].x - e[y].x) + (double)(e[x].y - e[y].y) * (e[x].y - e[y].y)));
}
int main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (ll i = 1; i <= n; i++)
    {
        ll x, y;
        cin >> x >> y;
        e[i] = {x, y};
    }
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = i + 1; j <= n; j++)
        {
            double k = gap(i, j);
            edges[s++] = {i, j, k};
        }
    }
    for (ll i = 1; i <= m; i++)
    {
        ll u, v;
        cin >> u >> v;
        for (ll j = 1; j < s; j++)
        {
            if(u == edges[j].a && v == edges[j].b)
            {
                edges[j].w = 0.0;
            }
        }
    }
    double t = kruskal();
    printf("%.2lf", t);
    return 0;
}
2023/9/5 22:33
加载中...