题意：有n个点，q个套餐，求连接所有的点的最小花费。
题解：用二进制枚举每个套餐，然后跑Kruskal（）。。。。。这种写法应该会超时的，可能数据太水了。。。。
1 #include<vector> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 8 const int maxn=1005; 9 struct edge{ 10 int u,v,cost; 11 bool operator<(const edge& i)const{ 12 return cost<i.cost; 13 } 14 }es[maxn*maxn]; 15 16 int q,n,m,kq,kase; 17 int F[maxn],most[10],x[maxn],y[maxn]; 18 vector<int> G[10]; 19 20 int Find(int a){ 21 if(a!=F[a]) F[a]=Find(F[a]); 22 return F[a]; 23 } 24 25 bool unite(int a,int b){ 26 int x=Find(a),y=Find(b); 27 if(x==y) return false; 28 else{ F[x]=y; return true; } 29 } 30 31 void read(){ 32 scanf("%d%d",&n,&q); 33 for(int i=1;i<=q;i++) G[i].clear(); 34 for(int i=1;i<=q;i++){ 35 scanf("%d%d",&kq,&most[i]); 36 for(int j=1;j<=kq;j++) { 37 int temp; 38 scanf("%d",&temp); 39 G[i].push_back(temp); 40 } 41 } 42 for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); 43 } 44 45 void init(){ 46 m=0; 47 for(int i=1;i<=n;i++){ 48 for(int j=i+1;j<=n;j++){ 49 es[m].u=i,es[m].v=j; 50 int temp=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); 51 es[m++].cost=temp; 52 } 53 } 54 sort(es,es+m); 55 } 56 57 int Kruskal(){ 58 int ans=0,num=0; 59 for(int i=0;i<m&&num<n-1;i++){ 60 if(unite(es[i].u,es[i].v)){ 61 num++; 62 ans=ans+es[i].cost; 63 } 64 } 65 return ans; 66 } 67 68 void solve(){ 69 for(int i=1;i<=n;i++) F[i]=i; 70 71 int ans=Kruskal(); 72 for(int i=0;i<(1<<q);i++){ 73 int sum=0; 74 for(int j=1;j<=n;j++) F[j]=j; 75 for(int j=1;j<=q;j++){ 76 if((i>>(j-1))&1) continue; //key point!!! 77 sum=sum+most[j]; 78 for(int k=1;k<G[j].size();k++) unite(G[j][k],G[j][0]); 79 } 80 ans=min(ans,sum+Kruskal()); 81 } 82 cout<<ans<<endl; 83 } 84 85 int main() 86 { cin>>kase; 87 while(kase--){ 88 read(); 89 init(); 90 solve(); 91 if(kase) cout<<endl; 92 } 93 return 0; 94 }