这道题是一道最小生成树问题的题，与最原始的最小生成树不同的是，问题中添加了套餐，不过我们发现套餐的数量很小(<=8)，所以我们可以枚举选择那些套餐，然后再次基础上进行最小生成树(Kruskal)，下面是代码，我们需要注意的是由于边的数量很多，所以我们已经连n-1条边时我们就不用考虑后面了。
代码：
// UVa 1151 #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int maxp = 10; const int maxn = 1000 + 5; const int maxm = 500000 + 5; const int INF = 100000000; int n, p, best; int x[maxn], y[maxn], fa[maxn], cnt; struct Item { vector<int> nodes; int val, size; } item[maxp]; struct Edge { int u, v, val; Edge(int u=0, int v=0, int val=0) : u(u), v(v), val(val) {} bool operator < (const Edge& rhs) const { return val < rhs.val; } } edge[maxm]; int dist(int a, int b) { return (x[a]-x[b]) * (x[a]-x[b]) + (y[a]-y[b]) * (y[a]-y[b]); } void init() { for (int i = 1; i <= n; ++i) fa[i] = i; } int find(int x) { return x == fa[x] ? x : x = find(fa[x]); } int Kruskal(int set) { init(); int ans = 0, u, count = 0; for (int i = 0; i < p; ++i) if (set&(1<<i)) { ans += item[i].val; u = find(item[i].nodes[0]); for (int j = 1; j < item[i].size; ++j) { int v = find(item[i].nodes[j]); if (v != u) fa[v] = u; } } if (ans > best) return best; for (int i = 0; i < cnt; ++i) { int x = find(edge[i].u), y = find(edge[i].v), val = edge[i].val; if (x != y) { ans += val; fa[x] = y; if (++count == n-1) break; } if (ans > best) return best; } return ans; } int main() { int T, kase; scanf("%d", &T); for (int kase = 0; kase < T; ++kase) { if (kase) printf(" "); scanf("%d%d", &n, &p); for (int i = 0; i < p; ++i) { scanf("%d%d", &item[i].size, &item[i].val); item[i].nodes.clear(); for (int j = 0; j < item[i].size; ++j) { int k; scanf("%d", &k); item[i].nodes.push_back(k); } } for (int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]); cnt = 0; for (int i = 1; i <= n; ++i) for (int j = i+1; j <= n; ++j) edge[cnt++] = Edge(i,j,dist(i,j)); sort(edge, edge+cnt); best = INF; for (int i = 0; i < (1<<p); ++i) best = min(best, Kruskal(i)); printf("%d ", best); } return 0; }
当已经连通的边为n-1时，我们就能够退出，然而时间复杂度是O(2^q*n^2+n^2logn)，比较容易超时，然而我提交后竟然过了，所以数据出的很"和谐"，那么如果出题人想要难为我们，他就可以尽量不满足n-1这个条件，就是让n-1个点很近，然而最后一个点非常的远，这样我们退出就需要等到最后了。
所以我们需要优化算法，我们发现，对于选择边(选完套餐时候)，我们也是尽量选择小的边，而无关紧要的边我们能不能提前排除呢？
我们首先需要忽略套餐的条件，进行一次“裸”的Kruskal,然后将连通图的边确定下来，后面我们枚举套餐时仅仅考虑确定下来的边，这是因为我们选择一定的套餐时，套餐包含的边被视为“0”，于是相当于进行一次新的Kruskal，这样后面的边仍然不会被选中。
下面是代码：
// UVa 1151 #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> using namespace std; const int maxn = 1000 + 5; const int maxp = 8; int n, p; int x[maxn], y[maxn], cost[maxp]; vector<int> subn[maxp]; int pa[maxn]; int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); } struct Edge { int u, v, d; Edge(int u=0, int v=0, int d=0) : u(u), v(v), d(d) {} bool operator < (const Edge& rhs) const { return d < rhs.d; } }; int dist(int a, int b) { return (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]); } int MST(int cnt, const vector<Edge>& a, vector<Edge>& b) { if (cnt == 1) return 0; b.clear(); int ans = 0, m = a.size(); for (int i = 0; i < m; ++i) { int u = findset(a[i].u), v = findset(a[i].v), d = a[i].d; if (u != v) { ans += d; pa[u] = v; b.push_back(a[i]); if (--cnt == 1) break; } } return ans; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &p); for (int i = 0; i < p; ++i) { int cnt; scanf("%d%d", &cnt, &cost[i]); subn[i].clear(); while (cnt--) { int u; scanf("%d", &u); subn[i].push_back(u-1); } } for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]); vector<Edge> e, need; for (int i = 0; i < n; ++i) for (int j = i+1; j < n; ++j) e.push_back(Edge(i, j, dist(i,j))); for (int i = 0; i < n; ++i) pa[i] = i; sort(e.begin(), e.end()); int ans = MST(n, e, need); for (int i = 0; i < (1<<p); ++i) { int c = 0, cnt = n; for (int j = 0; j < n; ++j) pa[j] = j; for (int j = 0; j < p; ++j) if (i&(1<<j)) { c += cost[j]; for (int k = 1; k < subn[j].size(); ++k) { int u = findset(subn[j][0]), v = findset(subn[j][k]); if (u != v) { pa[u] = v; --cnt; } } } vector<Edge> dummy; ans = min(ans, c + MST(cnt, need, dummy)); } printf("%d ", ans); if (T) printf(" "); } return 0; }