本文共 1180 字，大约阅读时间需要 3 分钟。

题目描述

万维网（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）

输出格式

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

思路：

因为最多只有8个"套餐"，所以我们用二进制枚举下每个套餐买与不买的状态，然后每一个状态跑一边最小生成树将没加入的点加入就可以了。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const int maxn=1e3+5;int t,n,q;int num[maxn];int coll[maxn][maxn];int sp[maxn];int posx[maxn],posy[maxn];int a[maxn];int ans=0x3f3f3f3f;int id;struct edge{    int u;    int v;    int len;};edge e[maxn*maxn];int compare (edge a,edge b){    return a.len
        
         >i)&1; if(t==0) continue; tans+=sp[i]; for (int j=1;j
        
       
      
     
    
   

转载地址：http://xzoen.baihongyu.com/