首页 > 代码库 > uva 1511 最小生成树

uva 1511 最小生成树

2024-11-26 00:40:02   203人阅读

https://vjudge.net/problem/UVA-1151

题意，给出N个点以及二维坐标，可以在任意两点间建立通路，代价是两点欧几里得距离的平方，同时有q个套餐，套餐x有qx个点，代价是qw，

花费qw就能将这qx个点全部相联通，套餐可以任意选择几种或不选，求将所有的点联通所要的最小代价。

很容易想到一个暴力做法，遍历2^q种套餐方案，将这些点提前加入后再跑kruskal，这样的复杂度有些高了。

其实简单证明一下，我们可以先不买套餐跑一遍kruskal，之后保存下来所选的边。

遍历所有q集合时发现，对于之前没有选到的边，现在加入了几条免费边之后，更不会选到（因为仅凭之前选的边就足以使得这条边无贡献），因为这条边加入后没有贡献，不会因为买套餐而变得有贡献，我们可以提前除去这些边，然后数据就很小了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int f[1005];
 4 int getf(int v){return f[v]==v?v:f[v]=getf(f[v]);}
 5 struct Edge
 6 {
 7     int u,v,w;
 8     bool operator<(const Edge& x)const{
 9     return w<x.w;
10     }
11 }e1[500005],e2[1005];
12 int x[1005],y[1005],cost[15];
13 int main()
14 {
15     int T,N,Q,n,m,xx,i,s,j,k;
16     //freopen("in.txt","r",stdin);
17     cin>>T;
18     while(T--){vector<int> G[10];
19     int m1=0,m2=0;
20         cin>>N>>Q;
21         for(i=0;i<Q;++i){
22             cin>>n>>cost[i];
23             while(n--){
24                 cin>>xx;
25                 G[i].push_back(xx);
26             }
27         }
28         for(i=1;i<=N;++i)
29         {
30             cin>>x[i]>>y[i];
31             for(j=1;j<i;++j)
32             {
33                 e1[m1].u=i;
34                 e1[m1].v=j;
35                 e1[m1++].w=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
36             }
37         }
38         for(i=0;i<=N;++i) f[i]=i;
39         sort(e1,e1+m1);
40         int ans=0;
41         s=0;
42         for(i=0;s<N-1&&i<m1;++i)
43         {
44             int fu=getf(e1[i].u),fv=getf(e1[i].v);
45             if(fv!=fu){
46                 e2[m2++]=e1[i];
47                 s++;
48                 f[fv]=fu;
49                 ans+=e1[i].w;
50             }
51         }
52         for(i=0;i<(1<<Q)-1;++i)
53         {
54             for(j=0;j<=N;++j) f[j]=j;
55             int sum=0; s=0;
56             for(j=0;j<Q;++j)
57             {
58                 if(i&(1<<j)){
59                     sum+=cost[j];
60                     for(int k=0;k<G[j].size()-1;++k){
61                         int fu=getf(G[j][k]),fv=getf(G[j][k+1]);
62                         if(fu!=fv){
63                             f[fv]=fu;
64                             s++;
65                         }
66                     }
67                 }
68             }
69             for(j=0;j<m2&&s<N-1;j++)
70             {
71               int fu=getf(e2[j].u),fv=getf(e2[j].v);
72               if(fu!=fv){
73                 s++;
74                 f[fv]=fu;
75                 sum+=e2[j].w;
76               }
77             }
78             ans=min(ans,sum);
79         }
80         cout<<ans<<endl;
81         if(T) cout<<endl;
82 
83     }
84     return 0;
85 }

 

uva 1511 最小生成树


联系
我们