题目链接

---

题意：平面上有n个点(1<=N<=1000)，你的任务是让所有n个点连通，为此，你可以新建一些边，费用等于两个端点的欧几里得距离的平方。另外还有q(0<=q<=8)个套餐，可以购买，如果你购买了第i个套餐，该套餐中的所有结点将变得相互连通，第i个套餐的花费为ci。求最小花费。

---

solution：

枚举每种套餐选或不选(二进制), 把选择的套餐中的每一个点都加入同一个联通分量中，再用Kruskal。

---

#include <cstdio> #include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; #define Inf 0x7fffffff const int N = 1100; struct P{ int x, y; }p[N]; struct Edge{ int u, v, w; }e[N*N]; int co[10], pa[N]; vector<int> G[10]; int n, m, q; int find(int x){ int r=x; while( r!=pa[r] ) r=pa[r]; int i=x, j; while( i!=pa[i] ){ j=pa[i]; pa[i]=r; i=j; } return r; } bool merge(int x, int y){ x=find(x), y=find(y); if( x==y ) return false; pa[x]=y; return true; } void reset(){ for ( int i=1; i<=n; i++ ) pa[i]=i; } int Kruskal(){ int sum=0, ret=0; for ( int i=0; i<m; i++ ) if( merge(e[i].u, e[i].v) && sum<n-1 ){ ret+=e[i].w; sum++; } return ret; } int dis( P a, P b ){ return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); } void solve(){ reset(); int ans=Kruskal(); // printf("\n%d\n", ans); for ( int i=0; i<(1<<q); i++ ){ reset(); int cost=0; for ( int j=0; j<q; j++ ){ if( (i>>j)&1 ) continue; cost+=co[j]; for ( int t=1; t<G[j].size(); t++ ) merge( G[j][t],G[j][0] ); } ans=min(cost+Kruskal(),ans); } printf("%d\n", ans); } int cmp(Edge a, Edge b){ return a.w<b.w; } int main(){ int T; int ca=1; scanf("%d", &T); while( T-- ){ if( ca>1 ) printf("\n"); ca++; scanf("%d%d", &n, &q ); m=0; for ( int i=0; i<q; i++ ){ G[i].clear(); int cnt; scanf("%d%d", &cnt, &co[i] ); for ( int j=1; j<=cnt; j++ ){ int tmp; scanf("%d", &tmp ); G[i].push_back(tmp); } } for ( int i=1; i<=n; i++ ) scanf("%d%d", &p[i].x, &p[i].y ); for ( int i=1; i<=n; i++ ) for ( int j=i+1; j<=n; j++ ){ e[m].u=i, e[m].v=j; e[m++].w=dis(p[i],p[j]); } // printf("\n"); sort(e,e+m,cmp); // for ( int i=0; i<m; i++ ) printf("%d %d %d\n", e[i].u, e[i].v, e[i].w ); solve(); } }