思路：
一开始用Kruskal超时了，因为这是一个稠密图，边的数量最惨可能N^2，改用Prim。
Prim是这样的，先选一个点（这里选1）作为集合A的起始元素，然后其他点为集合B的元素，我们要做的就是每次找到B中的一个点，满足这个点到A的权值是B到A的权值中最小的，然后我们把这个点加入到A，再更新B中的点到A的最小距离。
代码：
#include#include #include #include #include #define ll long longusing namespace std;const int N = 750+5;int mp[N][N]; //i j的距离int vis[N];int dis[N]; //点到集合的最小距离int lian[N];int n;struct node{ int x,y;}p[N];void init(){ for(int i = 1;i <= n;i++){ //建图 scanf("%d%d",&p[i].x,&p[i].y); for(int j = 1;j <= i;j++){ mp[i][j] = mp[j][i] = (p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y); } } int Q,a,b; scanf("%d",&Q); while(Q--){ scanf("%d%d",&a,&b); mp[a][b] = mp[b][a] = 0; } memset(vis,0,sizeof(vis)); //标记该点是否连接 for(int i = 1;i <= n;i++){ dis[i] = mp[i][1]; lian[i] = 1; //初始都和1的距离最小 } vis[1] = 1;}void Prim(){ for(int i = 1;i < n;i++){ //找n-1条边 int MIN = 100000005; int point; for(int j = 1;j <= n;j++){ if(!vis[j] && dis[j] < MIN){ MIN = dis[j]; point = j; } } vis[point] = 1; //找到了 if(mp[point][lian[point]] != 0) //为零是已经有路的 printf("%d %d\n",point,lian[point]); //点和他相连的点 for(int j = 1;j <= n;j++){ if(!vis[j] && mp[j][point] < dis[j]){ lian[j] = point; dis[j] = mp[j][point]; } } }}int main(){ scanf("%d",&n); init(); Prim(); return 0;}