wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
AtCoder agc002 D
2017-04-10 08:46:13
320
0
0
wuvin
## 题面描述 你有一个$N$个点$M$条边的带边权无向图，现在有Q个询问，每次询问给出三个数 $X_i,Y_i,Z_i$,询问如果两个人分别从$X_i,Y_i$出发，他们总共需要访问$Z_i$个点，行走的路径可以不是简单路径，那么他们访问的边的最大边权最小能使多少。 ## 数据范围 $N,M,Q \leq 10^5$ ## 题解 正解：整体二分+并查集 复杂度$O(NlogN)$ 首先我们二分一个答案$x$，然后做一遍，拿并查集连接连通块。然后接下来所有询问分为，答案比$x$大的和答案比$x$小的。如果答案比$x$大，那么这些边一定早就被加入了，那么把没有加入的边和那些答案比$x$大的丢在右边，同理答案比$x$小的和已经加入的边丢到左边就可以了。然后递归下去即可。 我的思路： 并查集+二分+倍增 复杂度$O(Nlog^2N)$ 按照权值顺序加边，然后记录一个合并树，也就是树上每一个节点是一个集合，两个集合在他们LCA出合并，叶子节点就是单点。记录每一个点的集合大小和边的最值。然后对于一对点$(X_i,Y_i)$，如果他们在LCA处还没有达到$Z_i$，那么答案一定在祖先，从LCA开始倍增即可。如果在LCA之下，那么二分一个解，然后倍增即可。感觉复杂度不是很优美。 我的思路2：并查集+二分+主席树 复杂度$O(NlogN)$ 那么我们来维护每个点到根的值域线段树，这样可以在线段树上走下去就可以了。 
上一篇:
Vim常用命令
下一篇:
SCOI2017酱油记
0
赞
320 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册