Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj2407探险&&4398福慧双修

写在前面

双倍经验爽翻天啊哈哈

题目链接

双倍经验给一道了
传送门

一句话题意

给你一堆双向边 两个方向的权值并不相同
一条路只能走一次
求从1出发回到1最短路(不能不走

题解

当然这个题有一种很多人都能想到的做法
当你从1走出来之后 以后的事情就变成了到1的最短路
但是
这个和暴力有什么区别?
复杂度来看并没有

正解
构建的思想
这个题中所有的边我们手动分为三种
反正我也不太会
以下所有的边表示:(a,b,c)表示a->b这条边长度为c
该边为(u,1,w) ,即从u点连向原点的边
1.若 u != p[u] 说明从原点到达点u的最短路径中没有经过边(1,u),
即边(u,1)可以被使用,此时存在一条原点S -> p[u] -> … -> u -> S 的路径
在新图中直接创建一条 (S,T, d[u]+w)的边
若u == p[u] 说明到达点u的最短路径是由边(1,u)得到,所以不能通过d[u]+w的方式返回原点。 但如果存在其他方式到达点u,则可以通过该边返回,故在新图中创建边(u,T,w)

2: 该边为(1,v,w) 即该边为从原点出发的边
若p[v]=v,即说明原点到达点v的最短路径即为(1,v,w),故此时不再添加边
若p[v]!=v,说明原点到达点v的最短路径不是(1,v,w),此时需要在新图中添加边(1,v,w)

3: 该边为(u,v,w) (u != 1 && v != 1)
若p[u] != p[v],说明从原点到达点u的最短路径,与从原点到达点v的最短路径不同,即存在S -> p[u] -> u -> v 的路径,创建边(1,v,d[u]+w)
若p[u] == p[v],则在新图中保留原边 (u,v,w)

这样的话新图就建出来了
在新图上面跑T最短路就行了

本内容2018.3.16更新

多亏了assass_cannotin的二叉堆模板
assass_cannotin二叉堆模板
我直接两道题到了rk1


这个不给代码
免得被卡掉

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏