题目简述
在平面上给定 $n$ 个点的坐标，你可以用一条线段连接任意两个点，使它们联通，代价为其长度的平方；平面上还有几 $m$ 个简单的多边形，第 $i$ 个多边形包含给出的点中的 $k$ 个，你可以给多边形染色使多边形里的点联通，代价是 $c_i$。求所有点联通的最小代价。
$n≤1000,\ m≤10$
思路
看到数据范围里的 $m$ 了嘛？这范围不是状压是啥啊！考场上注意到数据范围却没有想到状压的 potatoler 是屑
$n$ 的范围也不大，于是可以放心给点连边，如果没有多边形染色的限定的话就是一个简单的最小生成树板子啦！考虑多边形的染色对最小生成树的影响 —— 染过色的多边形，其内部的点之间不再受到最小生成树的约束，但是值得注意的是，多边形染色只会使原来在最小生成树中的边不再需要，而不能是本不在原图最小生成树中的边被选中。也就是说我们可以先求原图的最小生成树然后在考虑那些边需要留那些边不需要留。
考虑求最小生成树的算法流程：将边按权从小到大排序之后遍历，用一个并查集维护最小生成树的联通性 —— 这样可以在生成树联通的情况下保证边权和最小。给多边形染色之后相当于其中的有一些点已经联通，不需要在用最小生成树中的边了 —— 于是我们可以状压记录多边形的染色状态，对于每一种状态，初始化并查集使得染过色的多边形内部的点联通，然后像求最小生成树一样做就可以了。
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#define int long long
using namespace std;
const int MaxN = 2003;
int n, m, cntEdge, tot, ans;
int x[MaxN], y[MaxN], father[MaxN];
int cost[15];
vector<int> block[15];
class Edge{
public:
int from, to, value;
Edge() = default;
Edge(int u, int v){
from = u, to = v;
value = (x[u]-x[v]) * (x[u]-x[v]) + (y[u]-y[v]) * (y[u]-y[v]);
}
inline bool operator < (const Edge &b) const {
return value < b.value;
}
}graph[MaxN*MaxN], MST[MaxN];
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
inline int Find(int a){
return father[a] == a? a : father[a] = Find(father[a]);
}
inline void Init(){
for(int i=1; i<=n; i++)
father[i] = i;
tot = 0;
for(int i=1; i<=cntEdge; i++){
if(Find(father[graph[i].from]) == Find(father[graph[i].to])) continue;
father[Find(father[graph[i].from])] = Find(father[graph[i].to]);
ans += graph[i].value;
MST[++tot] = graph[i];
if(tot == n-1) break;
}
return;
}
inline void Solve(int s){
int sum = 0;
for(int i=1; i<=n; i++)
father[i] = i;
for(int i=1; i<=m; i++){
if(!(s & (1<<(i-1)))) continue;
sum += cost[i];
for(int j=0; j<block[i].size(); j++){
if(Find(block[i][j]) != Find(block[i][0])) father[Find(block[i][j])] = Find(block[i][0]);
}
}
for(int i=1; i<n; i++){
if(Find(father[MST[i].from]) == Find(father[MST[i].to])) continue;
father[Find(father[MST[i].from])] = Find(father[MST[i].to]);
sum += MST[i].value;
}
ans = min(ans, sum);
}
signed main(){
n = Read(), m = Read();
for(int i=1; i<=n; i++)
x[i] = Read(), y[i] = Read();
for(int i=1; i<n; i++)
for(int j=i+1; j<=n; j++)
graph[++cntEdge] = Edge(i,j);
sort(graph+1, graph+1+cntEdge);
Init();
for(int i=1; i<=m; i++){
int k = Read();
cost[i] = Read();
while(k--){
int ver = Read();
block[i].push_back(ver);
}
}
for(int i=1; i<(1<<m); i++)
Solve(i);
printf("%lld", ans);
return 0;
}