UVA1151

//感觉刘汝佳老师的思维真的太厉害了orz/*摘录书上的一段话： 只需一个小小的优化即可降低时间复杂度：先求一次原图（不购买任何套餐）的最小生成树，得到n-1条边，然后每次枚举完套餐后只考虑套餐中的边和这n-1条边，则枚举套餐之后再求最小生成树时，图上的边已经寥寥无几。为什么可以这样呢？首先回顾一下，在Kruskal算法中，哪些边不会进入最小生成树。答案是：两端已经属于同一个连通分量的边。买了套餐以后，相当于一些边的权变为0，而对于不在套餐中的每条边e，排序在e之前的边一个都没少，反而可能多了一些权值为0的边，所以在原图Kruskal时被“扔掉”的边，在后面的Kruskal中也一样会被扔掉。*/// UVa1151 Buy or Build// Rujia Liu#include<cstdio>#include<cmath>#include<cstring>#include<vector>#include<algorithm>using namespace std; + ;;int n;int x[maxn], y[maxn], cost[maxq];vector<int> subn[maxq];int pa[maxn];int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; } struct Edge {  int u, v, d;  Edge(int u, int v, int d):u(u),v(v),d(d) {}  bool operator < (const Edge& rhs) const {    return d < rhs.d;  }};// initialize pa and sort e before calling this method// cnt is the current number of componentsint MST(int cnt, const vector<Edge>& e, vector<Edge>& used) {  //找出原图跑一边kruskal之后用过的边  ) ;  int m = e.size();  ;  used.clear();  ; i < m; i++) {    int u = findset(e[i].u), v = findset(e[i].v);    int d = e[i].d;    if(u != v) {      pa[u] = v;      ans += d;      used.push_back(e[i]);      ) break;    }  }  return ans;}int main() {  int T, q;  scanf("%d", &T);  while(T--) {    scanf("%d%d", &n, &q);    ; i < q; i++) {      int cnt;      scanf("%d%d", &cnt, &cost[i]);      subn[i].clear();      while(cnt--) {        int u;        scanf("%d", &u);        subn[i].push_back(u-);      }    }    ; i < n; i++) scanf("%d%d", &x[i], &y[i]);    vector<Edge> e, need;    ; i < n; i++)      ; j < n; j++) {        int c = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);        e.push_back(Edge(i, j, c));      }    ; i < n; i++) pa[i] = i;    sort(e.begin(), e.end());    int ans = MST(n, e, need);    ; mask < (<<q); mask++) {  //枚举套餐，二进制法      // union cities in the same sub-network      ; i < n; i++) pa[i] = i;      ;      ; i < q; i++) <<i)) {        c += cost[i];        ; j < subn[i].size(); j++) {          ]);          if(u != v) { pa[u] = v; cnt--; }        }      }      vector<Edge> dummy;      ans = min(ans, c + MST(cnt, need, dummy));    }    printf("%d\n", ans);    if(T) printf("\n");  }  ;}