标题指的边集是说这道题的套餐， 是由几条边构成的。
思路是先做一遍最小生成树排除边， 因为如果第一次做没有加入的边， 到后来新加入了很多权值为0的边，这些边肯定排在最前面，然后这条边的前面的那些边肯定都要再扫一遍， 也就是这条边无论如何都不会选。
那么后来就是二进制枚举套餐， 从头开始， 加入套餐中的边然后权值加上套餐的权值， 然后把之前筛选下来的边做kruskal就ok了。
注意要对数据范围敏感， 这里套餐最多也就8个所以可以二进制枚举子集。
#include<cstdio>
#include<vector>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123;
int x[MAXN], y[MAXN], f[MAXN];
int cost[MAXN], n, m, q, cnt, sum;
struct node
{int u, v, w;node(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}bool operator < (const node& rhs) const{return w < rhs.w;}
};
vector<node> Edge, need;
vector<int> k[9];int find(int x)
{if(f[x] != x)f[x] = find(f[x]);return f[x];
}int solve()
{int ret = 0;REP(i, 0, need.size()){int u = find(need[i].u), v = find(need[i].v);if(u != v){f[u] = v;ret += need[i].w;if(--cnt == 1) break;}}return ret;
}int main()
{int T;scanf("%d", &T);while(T--){Edge.clear(); need.clear();scanf("%d%d", &n, &q);REP(i, 0, q){int t, x; k[i].clear();scanf("%d%d", &t, &cost[i]);while(t--) {scanf("%d", &x);k[i].push_back(x); }}REP(i, 1, n + 1) scanf("%d%d", &x[i], &y[i]), f[i] = i;REP(i, 1, n + 1)REP(j, i + 1, n + 1){int t = (x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]);Edge.push_back(node(i, j, t));}sort(Edge.begin(), Edge.end());int ans = 0; cnt = n;REP(i, 0, Edge.size()){int u = find(Edge[i].u), v = find(Edge[i].v);if(u != v){need.push_back(Edge[i]);f[u] = v;ans += Edge[i].w;if(--cnt == 1) break; //注意是1 }}REP(num, 0, 1 << q){sum = 0; cnt = n; REP(i, 1, n + 1) f[i] = i;REP(i, 0, q)if(num & (1 << i)){sum += cost[i];REP(j, 0, k[i].size()){int u = find(k[i][j]), v = find(k[i][0]);if(u != v) f[u] = v, cnt--;}}sum += solve();ans = min(ans, sum);}printf("%d\n", ans);if(T) puts(""); }return 0;
}