UVA1151 买还是建 Buy or Build

    • 73通过
    • 272提交
  • 题目来源 UVA 1151
  • 评测方式 RemoteJudge
  • 标签 并查集 状态压缩,状压 生成树
  • 难度 省选/NOI-
  • 时空限制 3000ms / 0MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    买还是建(Buy or Build,UVA1151)

    题目描述

    万维网(WWN)是一家运营大型电信网络的领先公司。 WWN希望在Borduria建立一个新的网络,您需要帮助WWN确定如何以最低的总成本设置其网络。有几个本地公司运营着一些小型网络(以下称为子网),部分覆盖了Borduria的n个最大城市。 WWN希望建立一个连接所有n个城市的网络。 要实现这一目标,它可以从头开始在城市之间建设网络,也可以从本地公司购买一个或多个子网。 您需要帮助WWN决定如何以最低的总成本建设其网络。

    1、所有n个城市都给出其二维坐标

    2、存在q个子网。 如果q≥1,给出每个子网中连接的城市。(不用关心连接的形状)

    3、每个子网只能购买,不能被分割

    4、连接两个不相通的城市,必须建立一个边,其建设成本是城市之间欧几里德距离的平方。

    您的任务是决定购买哪些现有网络以及建设哪些边,使得总成本最低。

    输入格式

    输入文件的第一行是一个整数T,表示测试数据的组数。接下来是一个空白行。每两组测试数据之间也有一个空白行。

    对于每组测试数据:

    第一行是两个整数,分别是城市的总数n和子网的数量q,1≤n≤1000,0≤q≤8。城市的编号从1到n

    接下来q行,每行多个整数,第一个整数表示这个子网中的城市的数量m,第二个整数表示购买这个子网的费用(费用不超过2*10^6),剩下的m个整数表示这个子网包含的城市

    接下来n行,每行两个整数,表示第i个城市的坐标(坐标的数字范围是0到3000)

    输出格式

    对于每组测试数据输出一行,输出建设网络的总费用。每组输出之间用一个空行隔开

    Translated by @kevensice__

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    暂无测试点
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。