当前位置:首页 > 生成树 > 正文
GDKOI2021普及组Day1D旅行
884+

题目大意:n个点m条边,每条边有费用,请问从起点s开始,花费不超过w能到多少个点?(可以买票,买票后费用不超过票价的边都可以免费走)

解题思路

显然,有多少钱,就买多少票!因为超过w的边都走不了;买票后,不超过w的边都可以走!

对于一个询问,我们可以Flood Fill爆搜一遍;对于多个询问,每次都爆搜会超时,但如果能不重复搜索边即可高效解决问题。

我们可以按照边排序、询问的花费排序,每次询问,我们将不超过费用的边合并,用并查集统计集合大小,并依次回答即可。

(显然边不需要重复合并、最后按照询问的编号输出即可。)

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,

GDKOI2021普及组Day1D旅行:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!