首页 技术 正文
技术 2022年11月23日
0 收藏 449 点赞 2,077 浏览 1564 个字

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

分析:按照刘汝佳的思路做的。首先求一次本身的最小生成树值,然后枚举购买的套餐(二进制枚举),每次购买了之后,将其权值设为0,并且加进最小生成树。

 #include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=;
int x[maxn],y[maxn],p[maxn];
#define repu(i, a, b) for(int i = (a); i < (b); i++)
int bb[];
int tran(int h)
{
int i = ;
while(h)
{
bb[i] = h%;
i++;
h /= ;
}
return i;
}
int Find(int x)
{
return p[x]==x?x:p[x]=Find(p[x]);
}
struct edge
{
int u,v,w;
bool operator<(const edge&a)
const
{
return w<a.w;
}
} _e[maxn*maxn],e[maxn];
int q[][maxn],c[],t[];
int n,m,r,cnt;
void init()
{
m=cnt=;
}
ll kruscal()
{
ll ret=;
for(int i=; i<n; i++)///一共就只考虑n-1条边
{
int x=Find(e[i].u),y=Find(e[i].v);
if(x!=y)
{
ret += e[i].w;
p[x]=y;
}
}
return ret;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
scanf("%d%d",&n,&r);
repu(i,,r)
{
scanf("%d%d",&t[i],&c[i]);
repu(j,,t[i]+)
scanf("%d",&q[i][j]);
}
repu(i,,n+)
scanf("%d%d",&x[i],&y[i]),p[i]=i;
repu(i,,n)
repu(j,i+,n+)
_e[++m]=(edge)
{
i,j,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])
};
sort(_e+,_e+m+);
ll ans=;
repu(i,,m+)
{
int x = Find(_e[i].u),y = Find(_e[i].v);
if(x != y)
{
///自己没能想到的方案:
///存下最小生成树的边,而且每次求最小生成树的时候就直接用这些边求
e[++cnt]=_e[i];
ans+=_e[i].w;
p[x]=y;
}
}///本身的最小生成树
repu(b,,<<r)
{
int tt = tran(b);
ll ansx = ;
repu(i,,n+) p[i] = i;
repu(i,,tt)
{
if(bb[i])///如果是1就选该套餐
{
ansx += c[i];///枚举加哪个套餐,二进制枚举,最多就是2^8个
repu(j,,t[i]+)
{
int xx = Find(q[i][j-]);
int yy = Find(q[i][j]);
p[xx] = yy;///加入最小生成树
}
}
}
ansx += kruscal();
ans=min(ans,ansx);
}
printf("%lld\n",ans);
if(T) printf("\n");
}
return ;
}

每次求最小生成树的时候,都会加进去几条权值是0的边,一定会被选,剩下的边也一定会从裸求的最小生成树种找到。第一求的时候舍弃的边可以永远舍弃。

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141647.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:876 阅读:5,464
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,688
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,503
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:731 阅读:4,468
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:5,379
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,263
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站