题意：

平面上有n个点，现在要把它们全部连通起来。现在有q个套餐，如果购买了第i个套餐，则这个套餐中的点全部连通起来。也可以自己单独地建一条边，费用为两点欧几里得距离的平方。求使所有点连通的最小费用。

分析：

很明显，如果没有这些套餐的话，就是一个裸的MST。

可以枚举套餐的组合情况，然后把套餐中的边的权值置为0，再求MST。

在求MST的过程中，并不需要把所有的边都加进来。只要把原图的MST的那些边和套餐中的边加进来即可。

因为，对于不在原图的MST的边，购买套餐以后，按照权值排序，排在它之前的边不会减少，反而会因为购买套餐而在前面多出来一些权值为0的边。所以原图中被“淘汰”的边，在购买套餐后也一定会被“淘汰”。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5  6 const int maxn = 1000 + 10; 7 const int maxq = 8; 8 int n; 9 int x[maxn], y[maxn], cost[maxq];10 vector
         
           subn[maxq];11 12 int pa[maxn];13 int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }14 15 struct Edge16 {17     int u, v, d;18     Edge(int u, int v, int d):u(u), v(v), d(d) {}19     bool operator < (const Edge& rhs) const { return d < rhs.d; }20 };21 22 int MST(int cnt, vector
          
           & e, vector
           
            & used)23 {24 if(cnt == 1) return 0;25 int m = e.size();26 int ans = 0;27 used.clear();28 for(int i = 0; i < m; ++i)29 {30 int u = findset(e[i].u), v = findset(e[i].v);31 if(u != v)32 {33 pa[u] = v;34 ans += e[i].d;35 used.push_back(e[i]);36 if(--cnt == 1) break;37 }38 }39 return ans;40 }41 42 int main()43 {44 //freopen("in.txt", "r", stdin);45 int T;46 scanf("%d", &T);47 while(T--)48 {49 int q;50 scanf("%d%d", &n, &q);51 for(int i = 0; i < q; ++i)52 {53 int cnt;54 scanf("%d%d", &cnt, &cost[i]);55 subn[i].clear();56 while(cnt--)57 {58 int u;59 scanf("%d", &u);60 subn[i].push_back(u-1); //代码中节点的编号是从0开始的61 }62 }63 for(int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]);64 65 vector
            
              e, need;66 for(int i = 0; i < n; ++i)67 for(int j = 0; j < i; ++j)68 {69 int c = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);70 e.push_back(Edge(i, j, c));71 }72 73 for(int i = 0; i < n; ++i) pa[i] = i;74 sort(e.begin(), e.end());75 76 int ans = MST(n, e, need);77 for(int S = 0; S < (1<
             
               hehe; //这里只是为了调用函数，所以弄了一个无关紧要的参数91 ans = min(ans, c + MST(cnt, need, hehe));92 }93 94 printf("%d\n", ans);95 if(T) printf("\n");96 }97 98 return 0;99 }