题解 | #Freckles#

最小生成树的变体，没有给边的权重，而是给了节点信息。对于每一个节点对，可以计算出边的权重，然后再用kruskal算法解决。

#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

//习题11.4
const int maxn=1010;
int father[maxn];
int height[maxn];
struct edge{
    int node1;
    int node2;
    float dist;
};

struct node{
    float x;
    float y;
};

node nodelist[maxn];
edge graph[maxn*maxn];

//初始化
void initial(){
    for(int i=0;i<=maxn;i++){
        father[i]=-1;
        height[i]=0;
    }
}
//Find
int Find(int x){
    if (father[x]==-1)return x;
    return Find(father[x]);
}
//union
void Union(int x,int y){
    int fx=Find(x);
    int fy=Find(y);
    if (fx==fy)return;
    if(height[fx]>height[fy]){
        father[fy]=fx;
    }
    else if(height[fx]<height[fy]){
        father[fx]=fy;
    }
    else{
        father[fx]=fy;
        height[fy]++;
    }
}


int compare(edge x,edge y){
    return x.dist<y.dist;
}

//核心算法！！
float kruskal(int edgenumber){
    float sum=0;
    for(int i=0;i<edgenumber;i++){
        edge e=graph[i];
        if (Find(e.node1)!=Find(e.node2)){
            Union(e.node1,e.node2);
            sum+=e.dist;
        }
    }
    return sum;
}


int main(){
    int n;
    while(cin>>n){
        initial();
        for(int i=0;i<n;i++){
            cin>>nodelist[i].x>>nodelist[i].y;
        }
        int ed_id=0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                node n1=nodelist[i];
                node n2=nodelist[j];
                float dist=sqrt((n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y));
                graph[ed_id].dist=dist;
                graph[ed_id].node1=i;
                graph[ed_id].node2=j;
                ed_id++;
            }
        }
        sort(graph,graph+ed_id,compare);
        float sum=kruskal(ed_id);
        printf("%.2f\n",sum);
    }
    return 0;
}