先求出原图的最小生成树，然后枚举买哪些套餐，把一个套餐内的点相互之间边权为0，直接用并查集缩点。正确性是基于一个贪心，
在做Kruskal算法是，对于没有进入最小生成树的边，排序在它前面的边不会减少。
边比较多，用prim求最小生成树，效果比Kruskal好，枚举套餐的时候在用Kruskal。
prim和dijkstra的区别在于点距离的定义。
#includeusing namespace std;const int maxn = 1005;int n,q;int C[9];vector Buy[9];#define PB push_backint x[maxn],y[maxn];#define squ(x) ((x)*(x))int dist(int a,int b) { return squ(x[a]-x[b])+squ(y[a]-y[b]); }struct Edge{ int u,v,w; Edge(){} Edge(int u,int v,int w):u(u),v(v),w(w){} bool operator < (const Edge& x) const { return w > x.w; }}edges[maxn];bool EdgeLess(const Edge &x,const Edge &y) { return x.w < y.w; }int ecnt;int d[maxn];bool done[maxn];const int INF = 0x3f3f3f3f;int Prim(){ fill(d,d+n,INF); fill(done,done+n,0); ecnt = 0; priority_queue q; q.push(Edge(-1,0,0)); // dummy edge int tot = d[0] = 0; while(q.size()){ Edge x = q.top(); q.pop(); if(done[x.v]) continue; edges[ecnt++] = x; tot += x.w; done[x.v] = true; for(int i = 1; i < n; i++){ if(done[i]) continue; int cost = dist(x.v,i); if(d[i]>cost){ d[i] = cost; q.push(Edge(x.v,i,cost)); } } } return tot;}int pa[maxn];int Find(int x) { return x==pa[x]?x:pa[x]=Find(pa[x]); }void Union(int a,int b,int &cnt){ int s1 = Find(a),s2 = Find(b); if(s1 != s2){ pa[s1] = s2; cnt--; }}int Kruskal(int cnt){ if(!cnt) return 0; int ans = 0; for(int i = 1; i < ecnt; i++){ Edge &e = edges[i]; int s1 = Find(e.u), s2 = Find(e.v); if(s1 != s2) { ans += e.w; pa[s1] = s2; cnt--; if(!cnt) return ans; } } return ans;}int main(){ //freopen("in.txt","r",stdin); int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&q); for(int i = 0; i < q; i++){ int t; scanf("%d%d",&t,C+i); Buy[i].clear(); while(t--) { int c; scanf("%d",&c); Buy[i].PB(c-1); } } for(int i = 0; i < n; i++){ scanf("%d%d",x+i,y+i); } int ans = Prim(); sort(edges+1,edges+ecnt,EdgeLess); for(int mask = 1,M = 1<