首页 > 题解 > bzoj 3669 [Noi2014]魔法森林

bzoj 3669 [Noi2014]魔法森林

LCT练习。。

Description

为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M。初始时小E同学在号节点1,隐士则住在号节点N。小E需要通过这一片魔法森林,才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候,这条边上的妖怪就会对其发起攻击。幸运的是,在号节点住着两种守护精灵:A型守护精灵与B型守护精灵。小E可以借助它们的力量,达到自己的目的。
只要小E带上足够多的守护精灵,妖怪们就不会发起攻击了。具体来说,无向图中的每一条边Ei包含两个权值Ai与Bi。若身上携带的A型守护精灵个数不少于Ai,且B型守护精灵个数不少于Bi,这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击,他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事,小E想要知道,要能够成功拜访到隐士,最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。
Input

第1行包含两个整数N,M,表示无向图共有N个节点,M条边。 接下来M行,第行包含4个正整数Xi,Yi,Ai,Bi,描述第i条无向边。其中Xi与Yi为该边两个端点的标号,Ai与Bi的含义如题所述。 注意数据中可能包含重边与自环。

Output

输出一行一个整数:如果小E可以成功拜访到隐士,输出小E最少需要携带的守护精灵的总个数;如果无论如何小E都无法拜访到隐士,输出“-1”(不含引号)。

Sample Input

【输入样例1】

4 5

1 2 19 1

2 3 8 12

2 4 12 15

1 3 17 8

3 4 1 17
【输入样例2】
3 1

1 2 1 1
Sample Output

【输出样例1】

32

【样例说明1】

如果小E走路径1→2→4,需要携带19+15=34个守护精灵;

如果小E走路径1→3→4,需要携带17+17=34个守护精灵;

如果小E走路径1→2→3→4,需要携带19+17=36个守护精灵;

如果小E走路径1→3→2→4,需要携带17+15=32个守护精灵。

综上所述,小E最少需要携带32个守护精灵。
【输出样例2】

-1

【样例说明2】

小E无法从1号节点到达3号节点,故输出-1。

HINT

2<=n<=50,000

0<=m<=100,000

1<=ai ,bi<=50,000

题解

首先按照一个权ai排序,然后从小到大加边。由于1~n的通路一定是一棵生成树,可以用并查集判断两个点是否连通,并且用LCT维护这棵生成树。如果当前边的两个端点连通的话,那么找一下这两个点树链上的最大值bi,如果bi大于当前边的bi,那么就将这个大的砍掉,将这条边加上,否则的话不加边。

加完一条边了之后判断1和n的连通性,如果连通的话更新答案。

判断是否加边的话ai不会对其产生影响,因为如果1-n连通了当前的ai一定是最大的,如果之前就连通了的话之前一定已经更新过答案了。

实现

维护最大值的操作见上一篇

把每个边用n+i的点表示,链接两点就直接链接x到n+i,n+i到y

因为已经排好序了,相当于已经离散化了,a的边权是按编号大小递增的

这样siz里维护的就是数组的下标

我们按b的关键字排序,然后val从n+1到n+m存的各个边的边权

这样的话update就需要每次提取val的值

每次加边前判断一下边的两头是否连通:

不连通就link上,更新并查集

连通的话,找到这条路径上b最大的一条边,断掉,连上这条边。

每次加完边后,判断一下1,n的连通性,更新一下ans

 

代码

第二种思路

spfa

我们对a排序,枚举a,对于每一次枚举求b权最大值的最小值即可

跑M遍SPFA肯定超时无误。。。。

这里要用的SPFA的动态加点(边)法 我们每加一条边 就把边的两端点入队 继续SPFA 不用对f数组进行memset

这方法非常快 比LCT好写了不知多少 然后还有剪枝

剪枝1 每加一条边就SPFA自然很浪费 我们发现数据里有a<=30的点 那么很多边的a值会是重复的 我们把a值相同的点统统加入队列 然后SPFA一次解决

剪枝2 对于一条双向边 我们不必向队列中加两个点 我一开始写的是把f值小的加进去 因为小的可以更新大的 后来发现这样还是慢 就直接在主函数中更新f值大的 能更新就加入队列

这里用的堆优化spfa

images

luogu效率第一,超第二400ms+

images

bzoj第九名


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×