有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