Sirni题解(最小生成树,埃氏筛)(继 Liang-梁)
目录
前言
本篇是对Liang-梁的Sirni(最小生成树,埃氏筛)的后继博客。
通篇原文:https://blog.csdn.net/qq_37555704/article/details/97107653?tdsourcetag=s_pcqq_aiomsg
本文稍加修正,分析了一些错误。
题意
给你 n 个点,每个点有一权值 Pi,两点i,j的边权为min(Pi%Pj,Pj%Pi),求最小生成树。
数据范围:n<=1e5,Pi<=1e7
思路
以下是原文:
首先30分我们可以通过枚举两两连边后用 Kruskal 做,复杂度 O(n2logn2)
其实我们排序时还可以用类似桶排序的方法
用vector或者前向星存储边访问,但是还是会超时,却给我们正解提供思路,然后考虑正解,
我们记值域为 T=[1,1e7]
我们假设两个点 a,b 可以发现若 Pa≤Pb 那么取 min 时只可能取Pb%Pa
那我们如何决策呢首先我们可以将所有Pb=kPa 的点缩成一个点,保存最小的 Pa ,因为他们相连的代价为0,我们可以用类似埃氏筛的方法处理
然后场上所有 Pa,Pb 都是不同的且不存在倍数关系我们发现,算法瓶颈在于边太多了,于是考虑减少边的数量(即可以判断一些不会选的边提前去除), 怎么做呢
假设有三个点 a,b,c 满足 Pa < Pb < Pc并且 Pb=k∗Pa+s,Pc=k∗Pa+t(0< s <Pa) 那 a,b 连边代价为 s ; a,c连边代价为 t ;b,c 连边代价 q 虽然不知道是多少但有一个范围即 :0≤q≤t−s
给这三个点连边只有三种情况:1.a−b−c
代价w1:s+q , s≤w1≤t
2.b−a−c
代价w2: s+t,w2=s+t
3.a−c−b
代价 w3:t+q,t≤w3≤2∗t−s于是w<min(w2,w3)w1<min(w2,w3),k一定时,对于a,ab连边是最优的, b-c这条边我们会在对于b考虑时决策我们记 f(i,k) 表示
那我们发现就只把 k 枚举一遍找到最小一个满足Px=k∗Pa+s(0<s<Pa)的Px,i,x 连边即可
那么问题转化为 将P 数组在值域为[1,1e7]中bool标记,后对于一个值 x 快速找到在它右侧第一个出现的值,那么从右至左简单的Dp扫一遍即可
后面用 30分的第2种做法即可分析一下,由于 Pi 互不相同,那么枚举Pi的倍数时我们的边上限为 Tloglogn类似埃氏筛的时间复杂度,于是桶排序访问时间复杂度为 O(n+T)
那么总的时间复杂度为 O(Tloglogn)
相信大家仔细想想就会发现,若是强制缩点,一些数据是过不了的。
若是有Pj是Pi倍数的话,相当于 i 和 j 有一条权值为零的边,这样的边无论多连几条都没有关系,所以不如就把所有这样的边都先连上,然后再判断权值非零的边。
强制缩点指在上述边都连上情况下,把所有连通的点(无向,所以只要有边就连通)都 蹂 揉成一个点,也就是说,被缩进去的点的权值都不存在了,原作者认为这不影响边的判断。
但是,随便来一组数据就过不了,比如
4
6 18 9 7
若是缩点,最后就缩成了6,9,7,算出来是 3。实际上依次连 9——18——6——7最小,答案是1。
一些建议
要打这道题的人,给些建议:
- 卡常之类的不要过火,走错方向了。
- 用Kruskal做时,不要用优先队列,不要用vector,用数组+sort就行。
- 算DP时,最右边最大的DP值为inf。
最新文章
- [转] form.getForm().submit的用法及Ext.Ajax.request的小小区别
- Bootstrap滚动监听
- 二叉树计数(codevs 3112)
- MogileFS 的介绍(MogileFS 系列1)[分布式文件系统]
- mysql查找字符串出现位置
- C语言程序设计50例(二)(经典收藏)
- VxWorks 6.9 内核编程指导之读书笔记 -- 多任务
- Intel格式和AT&;T格式汇编区别
- Javascript对象的声明
- JS-DOM元素灵活查找
- Yii 中出现“<;?= ... ?>;”是什么意思?
- Navi.Soft31.任务管理器(定时同步+数据采集)
- Jmeter性能与接口自动化实战
- 绕过CDN查看网站真实IP的一些办法
- JavaScript对象复制(二)
- 20170712 SQL Server 日志文件收索
- Python全栈-数据库介绍与基本操作
- d3.select(this)不能用箭头函数
- ICMP隧道 ptunnle
- 如何判断Android设备是否为模拟器