专栏首页AI那点小事九度OJ——1144Freckles

九度OJ——1144Freckles

题目描述: 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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 04-树6 Complete Binary Search Tree (30分)

    A Binary Search Tree (BST) is recursively defined as a binary tree which has the...

    AI那点小事
  • 九度OJ——1154Jungle Roads

    The Head Elder of the tropical island of Lagrishan has a problem. A burst of ...

    AI那点小事
  • 寻找大富翁

    题目描述 浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁. 输入描述: 输入包含多组测试用例. 每个用例首先包含2个...

    AI那点小事
  • P2946 [USACO09MAR]牛飞盘队Cow Frisbee Team

    题目描述 After Farmer Don took up Frisbee, Farmer John wanted to join in the fun. He...

    attack
  • 04-树6 Complete Binary Search Tree (30分)

    A Binary Search Tree (BST) is recursively defined as a binary tree which has the...

    AI那点小事
  • UVA 11039-Building designing【贪心+绝对值排序】 UVA11039-Building designing

    UVA11039-Building designing Time limit: 3.000 seconds An architect wants to desi...

    Angel_Kitty
  • HDU-1003 Max Sum(动态规划,最长字段和问题)

    Max Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J...

    ShenduCC
  • LeetCode Weekly Contest 38解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • PAT 甲级 1068 Find More Coins(0,1背包)

    1068. Find More Coins (30) 时间限制 150 ms 内存限制 65536 kB 代码长度限制 16000 B ...

    ShenduCC
  • HDU 1074 Doing Homework(状压DP)

    Doing Homework Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券