源代码:
/*
3 2
10 10
10 0
30 0
*/
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
struct Node
{
int x, y;
} node[501];
struct Edge
{
int from, to;
double dis;
} edge[1300], minedge[1300];
double getdis(Node &a, Node &b)
{
int disx = abs(a.x - b.x), disy = abs(a.y - b.y);
return sqrt(disx * disx + disy * disy);
}
bool cmp(Edge &a, Edge &b)
{
return a.dis < b.dis;
}
int fa[501];
int find(int &x)
{
return fa[x] == x ? x : fa[x] = find(x);
}
bool merge(int &x,int &y)
{
int fx = find(x), fy = find(y);
if (fa[fx] == fy)
return true;
fa[fx] = fy;
return false;
}
int n, k;
int main()
{
ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> node[i].x >> node[i].y;
//建立边
int cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
{
if (i == j)
continue;
edge[cnt].from = i;
edge[cnt].to = j;
edge[cnt].dis = getdis(node[i], node[j]);
cnt++;
}
//kruskal
int cnt1 = 0;
double sum = 0;
sort(edge, edge+cnt, cmp);
for (int i = 0; i < cnt; i++)
if (!merge(edge[i].from, edge[i].to))
{
sum += edge[i].dis;
minedge[cnt1++] = edge[i];
}
sort(minedge, minedge+cnt1, cmp);
cnt1--;
while (k--)
{
sum -= minedge[cnt1].dis;
cnt1--;
}
cout << fixed << setprecision(2) << sum;
return 0;
}
控制台:
3 2
10 10
10 0
30 0
zsh: segmentation fault xxx
怎么办啊!!!