参考博客:
https://blog.csdn.net/qq_32680617/article/details/51537339
https://blog.csdn.net/u013480600/article/details/37969655
TLE代码
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define INF 0x7fffffff
#define N 755
struct P
{
int x;
int y;
P():x(0),y(0){}
};
struct Edge
{
int u,v;
double w;
Edge():u(0),v(0),w(0){}
bool operator < (const Edge&e)const
{
return w < e.w;
}
};
int a[N];
int rk[N];
int n;
int num;
P nod[N];
Edge edge[N * N];
double getDis(int i,int j)
{
double xd = double(nod[i].x - nod[j].x);
double yd = double(nod[i].y - nod[j].y);
return sqrt(xd * xd + yd * yd);
};
void init_edge()
{
int id = 0;
int e = n * n;
for(int i = 0; i <= e; ++i)
{
edge[i].w = INF;
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
id = (i - 1)* n +j;
edge[id].u = i;
edge[id].v = j;
edge[id].w = getDis(i,j);
if(i == j) edge[id].w = INF;
}
}
}
void init_set()
{
for(int i = 1; i <= n; ++i)
{
a[i] = i;
rk[i] = 0;
}
}
int find_set(int x)
{
int p = x;
while(a[p] != p)
{
p = a[p];
}
int tmp;
int now = x;
while(now != p)
{
tmp = a[now];
a[now] = p;
now = tmp;
}
return p;
}
void union_set(int x,int y)
{
if(rk[x] < rk[y])
{
a[x] = y;
}
else
{
a[y] = x;
if(rk[x] == rk[y])
{
++rk[x];
}
}
}
void kruskal()
{
int e = n * n;
sort(edge,edge + e + 1);
int u,v;
for(int i = 0; i <= e; ++i)
{
if(num == 1) break;
u = edge[i].u;
v = edge[i].v;
u = find_set(u);
v = find_set(v);
if(u != v)
{
union_set(u,v);
--num;
printf("%d %d
",edge[i].u,edge[i].v);
}
}
}
int main()
{
scanf("%d",&n);
num = n;
int x,y;
for(int i = 1; i <= n; ++i)
{
scanf("%d%d",&x,&y);
nod[i].x = x;
nod[i].y = y;
}
init_edge();
int m;
scanf("%d",&m);
init_set();
for(int i = 1; i <= m; ++i)
{
scanf("%d%d",&x,&y);
x = find_set(x);
y = find_set(y);
if(x != y)
{
union_set(x,y);
--num;
}
}
kruskal();
return 0;
}
超时的原因主要是：
1.不必要计算出double类型的距离，只需计算x^2 + y^2，达到边之间的比较效果即可，并且数据的约束不会超出int范围 。
2.n个点需要记录的边数为(n ( imes) (n-1)) (div) 2,而不是n ( imes) n，这样记录边，时间耗费减少一半。
AC代码
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define INF 0x7fffffff
#define N 755
struct P
{
int x;
int y;
P():x(0),y(0){}
};
struct Edge
{
int u,v;
int w;
Edge():u(0),v(0),w(0){}
bool operator < (const Edge&e)const
{
return w < e.w;
}
};
int a[N];
int rk[N];
int n;
int num;
int edge_num;
P nod[N];
Edge edge[N * N];
int getDis(int i,int j)
{
int xd = (nod[i].x - nod[j].x);
int yd = (nod[i].y - nod[j].y);
return xd * xd + yd * yd;
};
void init_edge()
{
int id = 0;
int e = n * n;
edge_num = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = i + 1; j <= n; ++j)
{
edge[edge_num].u = i;
edge[edge_num].v = j;
edge[edge_num].w = getDis(i,j);
++edge_num;
}
}
}
void init_set()
{
for(int i = 1; i <= n; ++i)
{
a[i] = i;
rk[i] = 0;
}
}
int find_set(int x)
{
int p = x;
while(a[p] != p)
{
p = a[p];
}
int tmp;
int now = x;
while(now != p)
{
tmp = a[now];
a[now] = p;
now = tmp;
}
return p;
}
void union_set(int x,int y)
{
if(rk[x] < rk[y])
{
a[x] = y;
}
else
{
a[y] = x;
if(rk[x] == rk[y])
{
++rk[x];
}
}
}
void kruskal()
{
int e = n * n;
sort(edge,edge + edge_num);
int u,v;
for(int i = 0; i < edge_num; ++i)
{
if(num == 1) break;
u = edge[i].u;
v = edge[i].v;
u = find_set(u);
v = find_set(v);
if(u != v)
{
union_set(u,v);
--num;
printf("%d %d
",edge[i].u,edge[i].v);
}
}
}
int main()
{
scanf("%d",&n);
num = n;
int x,y;
for(int i = 1; i <= n; ++i)
{
scanf("%d%d",&x,&y);
nod[i].x = x;
nod[i].y = y;
}
init_edge();
int m;
scanf("%d",&m);
init_set();
for(int i = 1; i <= m; ++i)
{
scanf("%d%d",&x,&y);
x = find_set(x);
y = find_set(y);
if(x != y)
{
union_set(x,y);
--num;
}
}
kruskal();
return 0;
}