题意：平面上有n个点(1<=N<=1000)，你的任务是让所有n个点连通，为此，你可以新建一些边，费用等于两个端点的欧几里得距离的平方。另外还有q(0<=q<=8)个套餐，可以购买，如果你购买了第i个套餐，该套餐中的所有结点将变得相互连通，第i个套餐的花费为ci。
kruskal：
先求一次原图的最小生成树，得到n-1条边，然后每次枚举完套餐后只考虑套餐中的边和这n-1条边，则枚举套餐之后再求最小生成树。
key:
kruskal算法中，那些两端已经属于同一个连通分量的边不会再加到生成树里面。
那么买了套餐后，相当于一些边的权变为0，而对于不在套餐中的每条边e，排序在e之前的边一个也没少，反而可能多了一些权值为0的边。
所以在 原图kruskal时被扔掉的边，在购买套餐后的Kruskal中也一样会被扔掉。
#include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstring> #include <cstdlib> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <stack> #include <algorithm> using namespace std; #define ll int #define _cle(m, a) memset(m, a, sizeof(m)) #define repu(i, a, b) for(int i = a; i < b; i++) #define repd(i, a, b) for(int i = b; i >= a; i--) #define sfi(n) scanf("%d", &n) #define pfi(n) printf("%d ", n) #define sfi2(n, m) scanf("%d%d", &n, &m) #define sfd2(n, m) scanf("%lf%lf", &n, &m) #define pfi2(n, m) printf("%d %d ", n, m) #define pfi3(a, b, c) printf("%d %d %d ", a, b, c) const int INF = 0x3f3f3f3f; #define maxn 1010 #define maxm 1500010 ll w[maxm]; int m; int r[maxm]; int u[maxm], v[maxm], p[maxn]; ll xx[maxn], yy[maxn]; int kb[maxn]; vector<int> f[9]; int n, q, num[9]; int c[9]; int cmp(const int i, const int j) { return w[i] < w[j]; } int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); } ll Kruskal1() { ll ans = 0; int len = 0; repu(i, 0, m) { int e = r[i]; int x = Find(u[e]); int y = Find(v[e]); if(x != y) { kb[len++] = e; ans += w[e]; p[x] = y; } } return ans; } ll Kruskal2() { ll ans = 0; int len = 0; int t = n - 1; repu(i, 0, n - 1) { int e = kb[i]; int x = Find(u[e]); int y = Find(v[e]); if(x != y) { ans += w[e]; p[x] = y; } } return ans; } int main() { int T; sfi(T); while(T--) { sfi2(n, q); m = 0; repu(i, 0, q) { int a; sfi2(num[i], c[i]); f[i].clear(); repu(j, 0, num[i]) sfi(a), f[i].push_back(a); } repu(i, 1, n + 1) scanf("%d%d", &xx[i], &yy[i]); repu(i, 1, n + 1) repu(j, 1 + i, n + 1) { w[m] = (xx[i] - xx[j]) * (xx[i] - xx[j]) + (yy[i] - yy[j]) * (yy[i] - yy[j]); u[m] = i; v[m] = j; //printf("%d %d %d %lf ", m, i, j, w[m]); m++; } repu(i, 1, n + 1) p[i] = i; repu(i, 0, m) r[i] = i; sort(r, r + m, cmp); ll minn = Kruskal1(); sort(kb, kb + n - 1, cmp); //printf("%lld ", minn); int lim = 1<<q; ll cc; repu(i, 1, lim) { cc = 0; repu(j, 1, n + 1) p[j] = j; repu(j, 0, q) if((1<<j) & i) if(num[j]) { cc += c[j]; int x = Find(f[j][0]); repu(k, 1, num[j]) { int y = Find(f[j][k]); if(x != y) p[y] = x; } //printf("%d %d ", i, j); } minn = min(minn, cc + Kruskal2()); //printf("%lld ", minn); } printf("%d ", minn); if(T) puts(""); } return 0; }