90分代码 第二个测试用例WA
查看原帖
90分代码 第二个测试用例WA
296321
lovedanpin楼主2022/7/3 11:10

有uu知道第二个测试用例是测的哪个吗?

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n, m, fa[1005], vis[1005], cnt, eu, ev, uu;
double ans, x[1005], y[1005];
double distance(int i, int j)
{
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}

struct Edge
{
    int u, v;
    double w;
} edge[500005];

int cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

int find(int x)
{
    while (x != fa[x])
        x = fa[x] = fa[fa[x]];
    return x;
}

void kruskal()
{
    sort(edge, edge + cnt, cmp);
    for (int i = 0; i < cnt; i++)
    {
        eu = find(edge[i].u);
        ev = find(edge[i].v);
        if (eu != ev)
        {
            ans += edge[i].w;
            fa[eu] = ev;
            vis[i] = 1;
            if (++uu == n - 1)
            {
                break;
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf%lf", &x[i], &y[i]);
    }
    cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            edge[cnt].u = i;
            edge[cnt].v = j;
            edge[cnt++].w = distance(i, j);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &eu, &ev);
        eu = find(eu);
        ev = find(ev);
        if (eu != ev)
        {
            fa[eu] = ev;
            if (++uu == n - 1)
            {
                break;
            }
        }
    }
    kruskal();
    printf("%.2f", ans);
    system("pause");
    return 0;
}

第二个WA

2022/7/3 11:10
加载中...