UVA1151 买还是建 Buy or Build

万维网（WWN）是一家运营大型电信网络的领先公司。 WWN希望在Borduria建立一个新的网络，您需要帮助WWN确定如何以最低的总成本设置其网络。有几个本地公司运营着一些小型网络（以下称为子网），部分覆盖了Borduria的n个最大城市。 WWN希望建立一个连接所有n个城市的网络。 要实现这一目标，它可以从头开始在城市之间建设网络，也可以从本地公司购买一个或多个子网。 您需要帮助WWN决定如何以最低的总成本建设其网络。 1、所有n个城市都给出其二维坐标 2、存在q个子网。 如果q≥1,给出每个子网中连接的城市。（不用关心连接的形状） 3、每个子网只能购买，不能被分割 4、连接两个不相通的城市，必须建立一个边，其建设成本是城市之间欧几里德距离的平方。 您的任务是决定购买哪些现有网络以及建设哪些边，使得总成本最低。

无

无