【uva 1151】Buy or Build(图论--最小生成树+二进制枚举状态)

时间:2022-09-14 04:24:42

题意:平面上有N个点(1≤N≤1000),若要新建边,费用是2点的欧几里德距离的平方。另外还有Q个套餐,每个套餐里的点互相联通,总费用为Ci。问让所有N个点连通的最小费用。(2组数据的输出之间要求有换行)

解法:利用二进制枚举套餐,时间复杂度是O(2QN2+N2logN)。关于时间复杂度,枚举:二进制枚举为2Q,Kruskal为ElogE≈E≈N2;边排序:ElogE≈E≈N2。总的相加。

紫书上提到一个优化:不加任何套餐跑一遍MST(最小生成树),没有选的边便删除掉,因为以后加了套餐之后也选不到它。

理解有点困难:由于Kruskal算法中不会进入MST的边是那些两端属于同一个连通分量的边,那么套餐里的点互相连通,相当于在原先MST的图上另外加了几条权值为0的边。这时可能超过N-1条边出现环,那么我们就要割掉权值最大的这个环里的边,留下较小的边。这样的MST就是除了套餐必要的费用之外的权值和最小的了。

P.S.如果比赛时想不明白,那就只能对拍了!

P.P.S.但我不知道为什么优化无论加不加时间都差不多,明明优化使时间复杂度变为了O(2QN+N2logN),2Q≈103,N=103,logN≈10,理应由O(106)变为O(103)啊。

下面附上我的加了优化的代码——

  1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7 const int N=1010,M=(int)1e6+10,Q=10,X=3010,D=(int)2e6+10;
8 typedef long long LL;
9
10 int n,q,m;
11 int fa[N];
12 struct hp{int c,t;int s[N];}b[Q];
13 struct vert{int x,y;}a[N];
14 struct edge{int x,y,d;}e[M];
15
16 LL mmin(LL x,LL y) {return x<y?x:y;}
17 int sq_dist(int i,int j) {return (a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);}
18 void ins(int id,int x,int y,int d) {e[id].x=x,e[id].y=y,e[id].d=d;}
19 bool cmp(edge x,edge y) {return x.d<y.d;}
20 int ffind(int x)
21 {
22 if (fa[x]!=x) fa[x]=ffind(fa[x]);
23 return fa[x];
24 }
25 LL MST()
26 {
27 int i,t=0;
28 int cnt=0;//0
29 LL ans=0;
30 sort(e+1,e+1+m,cmp);
31 for (i=1;i<=n;i++) fa[i]=i;
32 for (i=1;i<=m;i++)
33 {
34 int x=e[i].x,y=e[i].y;
35 int xx=ffind(x),yy=ffind(y);
36 if (xx!=yy)
37 {
38 fa[xx]=yy;
39 cnt++,ans+=e[i].d;
40 e[++t]=e[i];
41 if (cnt==n-1) break;
42 }
43 }
44 m=t;
45 return ans;
46 }
47 LL MST_2(int cnt)
48 {
49 int i;
50 LL ans=0;
51 for (i=1;i<=m;i++)
52 {
53 int x=e[i].x,y=e[i].y;
54 int xx=ffind(x),yy=ffind(y);
55 if (xx!=yy)
56 {
57 fa[xx]=yy;
58 cnt++,ans+=e[i].d;
59 if (cnt==n-1) break;
60 }
61 }
62 return ans;
63 }
64 int main()
65 {
66 int T,i,j,k;
67 scanf("%d",&T);
68 while (T--)
69 {
70 scanf("%d%d",&n,&q);
71 for (i=1;i<=q;i++)
72 {
73 scanf("%d%d",&b[i].t,&b[i].c);
74 for (j=1;j<=b[i].t;j++)
75 scanf("%d",&b[i].s[j]);
76 }
77 for (i=1;i<=n;i++)
78 scanf("%d%d",&a[i].x,&a[i].y);
79 m=0;
80 for (i=1;i<=n;i++)
81 for (j=i+1;j<=n;j++)
82 ins(++m,i,j,sq_dist(i,j));
83
84 LL ans=MST();
85 for (i=0;i<(1<<q);i++)//bracelet
86 {
87 for (j=1;j<=n;j++) fa[j]=j;
88 int cnt=0,h=0;
89 for (j=1;j<=q;j++)
90 if (i&(1<<(j-1)))
91 {
92 h+=b[j].c;
93 for (k=2;k<=b[j].t;k++)
94 {
95 int x=b[j].s[1],y=b[j].s[k];
96 int xx=ffind(x),yy=ffind(y);
97 if (xx!=yy) fa[xx]=yy,cnt++;
98 }
99 }
100 ans=mmin(ans,h+MST_2(cnt));
101 }
102 printf("%lld\n",ans);
103 if (T) printf("\n");
104 }
105 return 0;
106 }