UVA 10369 - Arctic Network-程序员宅基地

最小生成树问题,kruskal算法的变形。

代码如下:

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define MAXN1 500+10
#define MAXN 3000000

int z, n, s, m, x[MAXN1], y[MAXN1], u[MAXN], v[MAXN], p[MAXN1], r[MAXN];
double w[MAXN], flag[MAXN];

int cmp(const void *_p, const void *_q)
{
    int *p = (int *)_p;
    int *q = (int *)_q;
    return w[*p] > w[*q] ? 1: -1;
}
int find(int o) {
   return p[o] == o ? o : p[o] = find(p[o]);}
double kruskal()
{
    int q = 0;
    for(int i = 0; i <= m; i ++) p[i] = i;
    for(int i = 0; i <= z; i ++) r[i] = i;
    qsort(r, z, sizeof(r[0]), cmp);
    for(int i = 0; i < z; i ++)
    {
        int e = r[i]; int x1 = find(u[e]); int y1 = find(v[e]);
        if(x1 != y1) { p[x1] = y1;flag[q++] = w[e];}
    }
    return flag[q-s];
}
void init()
{
    while(~scanf("%d",&n))
        while(n --)
        {
            scanf("%d%d",&s,&m);
            for(int i = 1; i <= m; i ++)
                scanf("%d%d",&x[i],&y[i]);
            z = 0; 
            for(int i = 1; i <= m; i ++)
                for(int j = i+1; j <= m; j ++)
                {
                    u[z] = i; v[z] = j;
                    w[z++] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                }
            printf("%.2lf\n",kruskal());
        }
}
int main()
{
    init();
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/yuzhaoxin1008/article/details/44305485

智能推荐

Python利用abaqus2dyna将Abaqus关键字输入文件优雅地转换为LS-DYNA关键字输入文件的详细解析与实践_abaqus怎么和lsdyna连接-程序员宅基地

文章浏览阅读932次。在开始具体介绍如何使用 abaqus2dyna 之前,我们首先需要了解一些基础知识。1.1 Abaqus 关键字输入文件Abaqus 关键字输入文件(*.inp)是一个文本文件,包含了用于有限元分析的所有信息。它主要由头部、模型定义、加载、输出请求和结束四个部分组成。1.2 LS-DYNA 关键字输入文件LS-DYNA 关键字输入文件(*.k 或 *.key)也是一个文本文件,它包含了用于分析的所有信息。它的结构和 Abaqus 关键字输入文件类似,但关键字定义和参数设置有一定的差异。_abaqus怎么和lsdyna连接

java adsl 拨号_Java实现ADSL拨号上网-程序员宅基地

文章浏览阅读330次。import java.io.BufferedReader;import java.io.InputStreamReader;public class ConnectNetWork {/*** 执行CMD命令,并返回String字符串** @param strCmd* @return* @throws Exception*/public static String exeCmd(String st..._java adsl拨号

VAssistX 快捷键-程序员宅基地

文章浏览阅读303次。本文转自 VAssistX 常用快捷键函数跳转Alt + G - 函数定义和声明的跳转Alt + O - 在.h与.cpp文件中实现相互转换Alt + M - 列出当前文件所有的函数Ctrl + Tab - 切换标签查找Ctrl + F - 查找Ctrl + Shift + F - 在文件中查找F3 - 查找下一个Shift + F3 - 查找上一个Shift + Alt + O - 查找文件 (直接定位,更是对项目了心应手的表现)Shift + Alt + S - 查找符号 .

如何有效的关闭Win10/ win 11 自动更新? 方法最全_hp电脑win10英文版怎么不升级win11-程序员宅基地

文章浏览阅读1.5w次,点赞28次,收藏226次。5种Win10关闭自动更新方法,win11通用,亲测,2022可以永久关闭win10自动更新的方法,如果你在玩游戏或者办公时突然变得超级卡,那可能是Win10系统在后台更新了_hp电脑win10英文版怎么不升级win11

ubuntu16.04安装torch_ubuntu下载torch-程序员宅基地

文章浏览阅读6.3k次,点赞3次,收藏8次。下载torch安装包: git clone https://github.com/torch/distro.git torch --recursive安装依赖库: cd torch/ sudo bash install-deps安装好后会提示:Torch7’s dependencies have been installed安装torch:sudo ./install.sh安装到最后会提示是否将_ubuntu下载torch

BF548/BF547/BF549系列DSP的开发教程六:4*4键盘的设计原理和驱动源码-程序员宅基地

文章浏览阅读863次,点赞24次,收藏13次。BF548接4*4键盘,硬件设计原理和软件驱动源码,看本文。

随便推点

::在C++中的意思_c++ ::代表-程序员宅基地

文章浏览阅读934次。::表示作用域,和所属关系。class Aint A::test() //表示test是属于A类的。关于::的具体解析:::是运算符中等级最高的,它分为三种:1)global scope(全局作用域符),用法(::name)。2)class scope(类作用域符),用法(class::name)。3)namespace scope(命名空间作用域符),用法(namespace::n..._c++ ::代表

如何在Arcgis中对图斑进行自上而下,从左往右地编号_arcgis编号号从上到下,从左到右-程序员宅基地

文章浏览阅读3w次,点赞20次,收藏90次。在实际项目中,需要我们按照自上而下,从左往右的顺序为图斑编号,并且多数时候序号位数是确定的,针对这个问题我总结了一个自认为还算简便的方法。下面是具体的方法步骤:1、计算Xmin与Ymax。利用坐标进行排序,首先要算出坐标值。需要说明的是这里没有直接利用质心坐标而采用Xmin、Ymax进行排序,是因为质心坐标会遇到一种情况,就是当这个图斑很长或者很宽时,本应排在前面的序号,而因为质心靠后不得不被..._arcgis编号号从上到下,从左到右

mysql 数据类型_mysql表格的数据类型-程序员宅基地

文章浏览阅读1k次,点赞28次,收藏14次。选择合适的数据类型是很重要的。如要求存储精度较高时,应选择 DOUBLE类型。如果进行数值比较,最好使用 DECIMAL类型。 如果字符串是固定长度的,使用char,日期类型,就不适合字符串存储。TEXT 存储纯文本文件。BLOB主要存储图片、音频信息等_mysql表格的数据类型

Mac OS X 10.5 Leopard: Direcory Utility, The end of Netinfo-程序员宅基地

文章浏览阅读81次。其实,在OS X Tiger 10.4中,原来有两个应用程序一个叫NetInfo,一个是Directory Access一个主要用于管理本地用户的,另一个用来设置绑定网络Directory服务的,这次的Directory Utility是把这两个的功能合并了。 ...

MybatisPlusException: Error: Method queryTotal execution error._method querytotal execution error. at-程序员宅基地

文章浏览阅读1.2w次。先说明下情况,这是我自己遇到的一种情况。我创建的表存在着关键字:DESC下面贴下异常:(只贴部分,异常信息太多了没必要)org.mybatis.spring.MyBatisSystemException: nested exception is org.apache.ibatis.exceptions.PersistenceException: ### Error querying d..._method querytotal execution error. at

.Net桌面程序自动更新NAppUpdate-程序员宅基地

文章浏览阅读1k次。自动更新介绍我们做了程序,不免会有版本升级,这就需要程序有自动版本升级的功能。应用程序自动更新是由客户端应用程序自身负责从一个已知服务器下载并安装更新,用户唯一需要进行干预的是决定是否愿意现在或以后安装新的更新。客户端程序要完成自动更新必须要做三件事情:检查是否有更新;当发现有更新时,开始下载更新;当下载完成时,执行更新操作;分别分析一下这三个步骤: 1、检查更新..._nappupdate