题意：

　　要使n个点之间能够互通，要使两点直接互通需要耗费它们之间的欧几里得距离的平方大小的花费，这说明每两个点都可以使其互通。接着有q个套餐可以选，一旦选了这些套餐，他们所包含的点自动就连起来了，所需要做的就是连上还未通的即可，q<=8。可以多买。求最小生成树所需的代价。

 

思路：

　　与普通求MST不同的就是多了套餐，而且还可以多买。每个套餐有买或不买两种可能，那么有2⁸种可能，即256种。

　　如果不买套餐，至少需要求1次MST是确定的，这个复杂度已经是O(n*n)了。还得考虑哪些餐套可以搭配来买更便宜，那么就穷举这256种组合，每种组合来一次MST，但是不再需要O（n*n）了，只需要用第一次生成树时所挑出来的边即可。

　　具体做法是，将套餐内的所有点先连接（并查集），再用MST的边来一次kruscal（记得加上套餐费）。对于每个组合都这样做，就能求出结果了。

　　特别要注意：每两个输出结果之间要1个空行，末尾不需要再空行，否则出错。

 

 

1 #include 
      
         2 #define   LL long long  3 using namespace std;  4 const int N=1000+5;  5 const int INF=0x7f7f7f7f;  6 vector
       
         vect[10];  7 vector< pair
        
          > cor, e, tree;  8 int t, r, n, q, a, b;  9 int cost[10],  pre[N],  g[N][N];; 10  11 int cmp(pair
         
           a,pair
          
            b){
    return g[a.first][a.second]
           
             a,pair
            
              b ){ return (a.first-b.first)*(a.first-b.first) +(a.second-b.second)*(a.second-b.second) ;}//不需要开方 13 14 int find(int x){ return pre[x]==x? x: pre[x]=find(pre[x]);} //查 15 void joint(int a,int b){a=find(a),b=find(b);if(a!=b) pre[a]=b;} //并 16 17 18 19 LL kruscal() //将生成树的树边取出 20 { 21 for(int i=1; i<=n; i++) pre[i]=i; 22 int cnt=0; 23 LL sum=0; 24 for(int i=0; i
             
              =n-1) return sum; 35 } 36 } 37 return sum; 38 } 39 40 41 LL kruscal_2() //带套餐的 42 { 43 LL sum=0; 44 for(int i=0; i
              
               >=1; 77 cnt++; 78 } 79 ans=min(ans, sum+kruscal_2()); //再生成树 80 } 81 return ans; 82 } 83 84 int main() 85 { 86 freopen("input.txt", "r", stdin); 87 cin>>t; 88 while(t--) 89 { 90 cin>>n>>q; 91 for(int i=1; i<=q; i++) //每个套餐 92 { 93 scanf("%d%d",&a,&cost[i]); 94 vect[i].clear(); 95 while(a--) 96 { 97 scanf("%d",&r); 98 vect[i].push_back(r); 99 }100 }101 cor.clear();102 for(int i=0; i