九度OJ——1144Freckles

AI那点小事

发布于 2020-04-18 19:51:16

2680

发布于 2020-04-18 19:51:16

题目描述： In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad’s back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley’s engagement falls through. Consider Dick’s back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle. 输入： The first line contains 0 < n <= 100, the number of freckles on Dick’s back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle. 输出： Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles. 样例输入： 3 1.0 1.0 2.0 2.0 2.0 4.0 样例输出： 3.41

思路：这世道变相的Kruskal的应用题，图模型的结点是输入的顶点，图模型的边是每个不同点之间的距离。 AC代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;

typedef struct point{
    double x;
    double y;
}Vertex;

typedef struct edge{
    int start;
    int end;
    double len;
}Edge;

struct cmp{
    bool operator() (Edge e1,Edge e2){
        return e1.len>e2.len;
    }
};

const int MAX = 110;
int data[MAX],N;
double sum;
priority_queue<Edge,vector<Edge>,cmp> Q;
Vertex vertexes[MAX];

double Length(Vertex v1 ,Vertex v2)
{
    double len_x = v1.x-v2.x;
    double len_y = v1.y-v2.y;
    return sqrt(len_x*len_x+len_y*len_y);
}

//查找操作 
int Find(int root)
{
    if(data[root] < 0){
        return root;
    } 
    return data[root] = Find(data[root]);
}

//并操作 
void Union(int root1,int root2)
{
    root1 = Find(root1);
    root2 = Find(root2);
    if(root1 == root2){
        return;     
    }else if(root1 < root2){
        data[root1] += data[root2];
        data[root2] = root1;
        N--;
    }else{
        data[root2] += data[root1];
        data[root1] = root2;
        N--;
    }
}

double Kruskal()
{
    double sum = 0;
    while(!Q.empty()){
        Edge e = Q.top();
        Q.pop();
        int root1 = e.start;
        int root2 = e.end;
        if(Find(root1) != Find(root2)){
            sum += e.len;
            Union(root1,root2);
        }
        if(N == 1){
            break;
        }
    }
    return sum;
}

int main()
{
    while(cin>>N){
        while(!Q.empty()){
            Q.pop();
        }
        for(int i = 0 ; i < MAX ; i++){
            data[i] = -1;
        }
        for(int i = 1 ; i <= N ; i++){
            Vertex v;
            cin>>v.x>>v.y;
            vertexes[i] = v;
        }
        for(int i = 1 ; i <= N ; i++){
            for(int j = i+1 ; j <= N ; j++){
                Edge e;
                e.start = i;
                e.end = j;
                e.len = Length(vertexes[i],vertexes[j]);
                Q.push(e);
            }
        }
        sum = Kruskal();
        printf("%.2lf\n",sum);
    }

    return 0;
}