`

Uva 10034 - Freckles

    博客分类:
  • Uva
阅读更多
题目大意:给定n(0<n<=100)个点,用线把这n个点连起来,使得任意两点间均可达

题目分析:很明显,基本最少生成树问题。a[i][j],表示点i,j之间的距离,由于是稠密图,所以采用Prim算法。



//Uva 10034 - Freckles
//最小生成树问题,采用Prim算法
#include <iostream>
#include <cmath>
#include <cstdio>
#include <memory.h>
#define eps 1e-6
using namespace std;
const double INF=20000000.0;
const int maxn=110;
int n;
double a[maxn][maxn];//邻接矩阵
struct point
{
    double x;
    double y;
}p[maxn];
double dis(point p1,point p2)
{
    double x=p2.x-p1.x;
    double y=p2.y-p1.y;
    return sqrt(x*x+y*y);
}
double prim()
{
    double d[maxn];
    int visit[maxn];
    double sum=0;
    for(int i=0;i<n;i++)    d[i]=a[i][0];
    d[0]=0;
    memset(visit,-1,sizeof(visit));
    visit[0]=0;
    for(int i=1;i<n;i++)
    {
        //查找距已有集合最近的点
        double minv=INF;
        int v;
        for(int j=0;j<n;j++)
        {
            if(visit[j]&&d[j]<minv)     {minv=d[j];v=j;}
        }
        sum+=minv;
        visit[v]=0;
        //更新
        for(int j=0;j<n;j++)
        {
            if(visit[j]&&(d[j]>a[v][j]))   d[j]=a[v][j];
        }
    }
    return sum;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n;i++)    cin>>p[i].x>>p[i].y;
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
        for(int j=i;j<n;j++)
        {
            a[i][j]=dis(p[i],p[j]);
            a[j][i]=a[i][j];
        }
        printf("%.2lf\n",prim());
        if(t)   cout<<endl;
    }
    return 0;
}

分享到:
评论

相关推荐

    Freckles

    Freckles

    Freckles New Tabs HD Wallpapers Themes-crx插件

    雀斑墙纸的新标签页 最热门,最受欢迎的高清壁纸 每天更新,每天精彩。 雀斑是一种浅褐色小斑点,针尖至米粒大小,常出现于前额、鼻梁和脸颊等处,偶尔也会出现于颈部、肩部、手背等处。为常染色体显性遗传,尤以...

    wheel-0.13.0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    三菱PLC例程源码ST反弹限位器焊机14

    三菱PLC例程源码ST反弹限位器焊机14本资源系百度网盘分享地址

    asp代码asp教师信息管理系统(源代码+论文)

    asp代码asp教师信息管理系统(源代码+论文)本资源系百度网盘分享地址

    tensorflow_serving_api_gpu-2.3.3-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    tensorflow_serving_api-2.0.0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    tensorflow_model_remediation-0.1.6.tar.gz

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    三菱PLC例程源码PID程序

    三菱PLC例程源码PID程序本资源系百度网盘分享地址

    tensorflow_recommenders-0.5.0-py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    基于ssm珠宝首饰交易平台.zip

    基于ssm珠宝首饰交易平台.zip

    tensorflow_protobuf-2.11.0-py3-none-any.whl

    算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    基于ssm的小区物业管理系统.zip

    基于ssm的小区物业管理系统.zip

    tensorflow_serving_api_gpu-2.2.0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    基于javaweb+ssm的企业人事信息管理系统.zip

    基于javaweb+ssm的企业人事信息管理系统.zip

    asp代码asp旅游信息管理系统(源代码+论文)

    asp代码asp旅游信息管理系统(源代码+论文)本资源系百度网盘分享地址

    WeRoBot-1.7.0-py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    三菱PLC例程源码步进对标定位

    三菱PLC例程源码步进对标定位本资源系百度网盘分享地址

    (完整word版)单片机_温度控制系统_外文翻译_外文文献_英文文献_中英翻译.doc

    (完整word版)单片机_温度控制系统_外文翻译_外文文献_英文文献_中英翻译.doc

    tensorflow_transform-0.1.8-py2-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

Global site tag (gtag.js) - Google Analytics