Freckles

题意：给出n个点和他们的坐标，用一支墨水笔将他们连通，要求墨水浪费最少

典型的最小生成树问题，用kruskal问题（包括并查集）

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef struct Node{
    int s; // 起点
    int d; // 终点
    double dis; // 距离
}Edge; // 边结构体
Edge E[4950]; // 100个点最多4950条边
int father[100];
int n; // 点个数
int cnt = 0; // 边个数
void init()
{
    for(int i = 0;i<n;i++)
        father[i] = i;
}
int findfather(int n)
{
    if(father[n] == n)
        return n;
    else
        return findfather(father[n]);
}

int cmp(const void*a,const void*b)
{
    Edge *x = (Edge *)a;
    Edge *y = (Edge *)b;
    return x->dis*1000 - y->dis*1000;
}
double kruskal()
{
    double ans = 0;
    qsort(E,cnt,sizeof(Edge),cmp);
    int j = 0; // 已添加的边的个数
    for(int i = 0;i<cnt;i++)
    {
        if(j == n-1)
            break;
        int x,y;
        //合并
        x = findfather(E[i].s);
        y = findfather(E[i].d);
        if(x!=y)
        {
            father[x] = y;
            ans += E[i].dis;
            j++;
        }
        else
            continue;
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    double c[n][2];
    init(); // father初始化
    for(int i = 0;i<n;i++)
        scanf("%lf%lf",&c[i][0],&c[i][1]);
    for(int i = 0;i<n;i++)
    {
        for(int j = i+1;j<n;j++)
        {
            E[cnt].s = i;
            E[cnt].d = j;
            E[cnt].dis = sqrt( (c[i][0]-c[j][0]) * (c[i][0]-c[j][0]) + (c[i][1]-c[j][1]) * (c[i][1]-c[j][1]) );
            cnt ++;
        }
    }
    printf("%.2lf",kruskal());
    return 0;
}