题意：平面上有n个点(1<=N<=1000)，你的任务是让所有n个点连通，为此， 你可以新建一些边，费用等于两个端点的欧几里得距离的平方。另外还有q(0<=q<=8)个套餐（数量小，可枚举），可以购买，如果你购买了第i个套餐，该套餐 中的所有结点将变得相互连通，第i个套餐的花费为ci。
分析：按照刘汝佳的思路做的。首先求一次本身的最小生成树值，然后枚举购买的套餐（二进制枚举），每次购买了之后，将其权值设为0，并且加进最小生成树。
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 #define ll long long
5 using namespace std;
6 const int maxn=1005;
7 int x[maxn],y[maxn],p[maxn];
8 #define repu(i, a, b) for(int i = (a); i < (b); i++)
9 int bb[260];
10 int tran(int h)
11 {
12 int i = 0;
13 while(h)
14 {
15 bb[i] = h%2;
16 i++;
17 h /= 2;
18 }
19 return i;
20 }
21 int Find(int x)
22 {
23 return p[x]==x?x:p[x]=Find(p[x]);
24 }
25 struct edge
26 {
27 int u,v,w;
28 bool operator<(const edge&a)
29 const
30 {
31 return w<a.w;
32 }
33 } _e[maxn*maxn],e[maxn];
34 int q[8][maxn],c[8],t[8];
35 int n,m,r,cnt;
36 void init()
37 {
38 m=cnt=0;
39 }
40 ll kruscal()
41 {
42 ll ret=0;
43 for(int i=1; i<n; i++)///一共就只考虑n-1条边
44 {
45 int x=Find(e[i].u),y=Find(e[i].v);
46 if(x!=y)
47 {
48 ret += e[i].w;
49 p[x]=y;
50 }
51 }
52 return ret;
53 }
54 int main()
55 {
56 int T;
57 scanf("%d",&T);
58 while(T--)
59 {
60 init();
61 scanf("%d%d",&n,&r);
62 repu(i,0,r)
63 {
64 scanf("%d%d",&t[i],&c[i]);
65 repu(j,1,t[i]+1)
66 scanf("%d",&q[i][j]);
67 }
68 repu(i,1,n+1)
69 scanf("%d%d",&x[i],&y[i]),p[i]=i;
70 repu(i,1,n)
71 repu(j,i+1,n+1)
72 _e[++m]=(edge)
73 {
74 i,j,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])
75 };
76 sort(_e+1,_e+m+1);
77 ll ans=0;
78 repu(i,1,m+1)
79 {
80 int x = Find(_e[i].u),y = Find(_e[i].v);
81 if(x != y)
82 {
83 ///自己没能想到的方案：
84 ///存下最小生成树的边,而且每次求最小生成树的时候就直接用这些边求
85 e[++cnt]=_e[i];
86 ans+=_e[i].w;
87 p[x]=y;
88 }
89 }///本身的最小生成树
90 repu(b,0,1<<r)
91 {
92 int tt = tran(b);
93 ll ansx = 0;
94 repu(i,1,n+1) p[i] = i;
95 repu(i,0,tt)
96 {
97 if(bb[i])///如果是1就选该套餐
98 {
99 ansx += c[i];///枚举加哪个套餐，二进制枚举，最多就是2^8个
100 repu(j,2,t[i]+1)
101 {
102 int xx = Find(q[i][j-1]);
103 int yy = Find(q[i][j]);
104 p[xx] = yy;///加入最小生成树
105 }
106 }
107 }
108 ansx += kruscal();
109 ans=min(ans,ansx);
110 }
111 printf("%lld\n",ans);
112 if(T) printf("\n");
113 }
114 return 0;
115 }View Code
每次求最小生成树的时候，都会加进去几条权值是0的边，一定会被选，剩下的边也一定会从裸求的最小生成树种找到。第一求的时候舍弃的边可以永远舍弃。