买还是建 Buy or Build

## 题目描述 万维网（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__

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=246&page=show_problem&problem=3592 [PDF](https://uva.onlinejudge.org/external/11/p1151.pdf)

1
7 3
2 4 1 2
3 3 3 6 7
3 9 2 4 5
0 2
4 0
2 0
4 2
1 3
0 5
4 4

17