MST ;

不过有 Q种 特殊方案，可以只花费C【i】 （0 < i < Q )

对于方案的选取，可以状态压缩

先直接生成MST ，并把边存起来；

枚举 状态

对于方案， 链接点， 如有剩下的点没有处理； 则剩下的边必会在原MST中的边选；

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn = 1000 + 31;struct Edges{    int x, y;    int val;    bool operator < (const Edges a) const { return val < a.val; }}E[maxn * maxn]; Edges Line[maxn]; int X[maxn],Y[maxn]; int Cost[maxn], st[10][maxn]; int Cnt,N,Q,Ans; int Pre[maxn]; int Find(int x) {     int r = x;     while(r != Pre[r]) r = Pre[r];     return Pre[x] = r; } bool Union(int x,int y) {     int ax = Find(x); int ay = Find(y);     if(ax == ay) return false;     Pre[ax] = ay;     return true; } void Init() {     for(int i = 0; i < maxn; ++i) Pre[i] = i; } void Solve(int Status); int main() {     ios::sync_with_stdio(false);     cin.tie(0);     int t;     cin >> t;     bool Jug = false;     while(t--)     {         if(Jug != false) cout <
         
          > N >> Q;         for(int i = 0; i < Q; ++i)         {             cin >> st[i][0] >> Cost[i];             for(int j = 1; j <= st[i][0]; ++j)                cin >> st[i][j];         }         for(int i = 1; i <= N; ++i)            cin >> X[i] >> Y[i];         Cnt = 0;         for(int i = 1; i < N; ++i)            for(int j = i+1; j <= N; ++j)         {            E[Cnt].x = i, E[Cnt].y = j;            E[Cnt++].val = (X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]);         }         sort(E,E+Cnt);         Init();         int ee = 0;         Ans = 0;         for(int i = 0; i < Cnt; ++i)         {             if(Union(E[i].x, E[i].y))             {                 Line[ee] = E[i];                 Ans += E[i].val;                 ee++;             }             if(ee == N-1) break;         }         for(int i = 1; i < (1<