最短路

最短路

这题看看就是叫你建边跑最短路的,但眨眼一看,哇赛,为什么这么多边!这样明显就是为了卡SPFA了。所以我们就要用到Dij算法去解答这题,Dij算法就是让当前路径最短的那个点去找边,减少枚举情况。具体如何去找当前路径最短的点,我们可以使用堆优化的Dij算法,但是呢规模还是太大呢,自己写的堆不够高效,所以我们要采用系统配对堆进行解答。 ......  查看更多

[Usaco2011 Jan]道路和航线

[Usaco2011 Jan]道路和航线
这题一眼看过去就是最短路呢,但是呢?好像有负环,啧啧Dij用不了啦!好像点有点多,Floyd用不了啦,就只剩下spfa啦,但是spfa在极限数据下还是会T掉呢?怎么办,这里引入Spfa其中一个优化SLF优化。全称Small Label First 策略
设要加入的节点是y,队首元素为x,若d[y] \lt d[x],则将y插入队首,否则插入队尾。
其实只要一个优化就可以了,但是为了测试多一下,我就再加了一个优化LLL优化,全称Large Label Last 策略
这样的话我们就可以用上双头队列deque了。
其他的就是普通跑一下spfa就好。
只有SLF优化的 ......  查看更多

最优贸易

最优贸易
这题主要是求一条路径上顺序的两个点的差的最大值,题目给出的边可能是单向边,也可能是双向边,对于求单一路径上最大值和最小值还是很好求的嘛,BFS一下我们就很好的求出这个答案了=v=。
但是怎么求两个顺序的点呢?
那么我们分解一下问题。
我们枚举每一个点,我们可以求出源点到这个点的最小价值路径,那么我们只需要看看有没有一条最大路径连到终点就好。
我们还可以重新连一次反向图,倒过来建边,然后从终点跑一次维护到每一个点的最大值,最后枚举每个点,最大最小值减一减就好。 ......  查看更多

Telephone Lines

Telephone Lines
简化一下题意,这题是在无向图上求出一条从1N的路径,使路径上第K+1大的边权尽量小。
这样的话我们可以发掘这题的金额是有二分性的,在合法的金额里面一定包含着最优金额,这样子我们就可以二分出最优金额进行求解,跑一下SPFA,金额大于mid的边边权为1,其他为0,最后判断一下d[ed]是否大于k就好,大于就是代表我现在金额不能完全修完前k条路径,然这题就解决了 ......  查看更多

「算进」[图论]最短路

图论是信息竞赛的一个极其重要的专题,那么,就先从图论里面最简单的最短路开始讲起。
对于一张有向图,我们一般采用的是邻接矩阵和邻接表两种储存路径的方式。对于一张无向图,我们可以把无向边看作两条方向相反的有向边,然后我们就可以把有向边和无向边加在一起储存了。
所以对于我们讨论图的最短路问题时,我们都以有向图为例设图G=(V,E)V是点集,E是边集。(x,y)代表从xy有一条边,他的边权为w(x,y),设n=|V|,m=|E|,邻接矩阵的大小为n^2
那么我们矩阵的时空复杂度为O(n^2)
假如我们用邻接表代码时,我们每一个点只记录一个边,每个边之后再记录一个边,就是类似HASH里面的链表一样。
那么邻接表的复杂度就会比邻接矩阵少的多,一般为O(n+m)
最短路有很多种算法如单多源最短路等。
那么就一个一个分析一下各种最短路的区别。 ......  查看更多

[Div1]「CodePlus 2018 4 月赛」最短路

[Div1]「CodePlus 2018 4 月赛」最短路
n \leq 100000,m \leq 500000的有向图,
两点之间还可以以a xor b的代价从ab,问st的最短路。
先两个点之间不走给定的边,最短路一定是直接ss到tt,
因为一个二进制的差异至少要被算一次。观察st的过程,
可以把这个过程完全等价地变成:一次只改一个二进制位,代价完全不变。
因此xor的边只用连nlog2(n)条,然后就无脑最短路了。 ......  查看更多

「CodePlus 2018 4 月赛」解题报告

比赛题目

[Div2]「CodePlus 2018 4 月赛」组合数游戏 [Div2]「CodePlus 2018 4 月赛」喵呜 [Div1][Div2]「CodePlus 2018 4 月赛」白金元首与七彩魔法 [Div1][Div2]「CodePlus 2018 4 月赛」组合数问题 2 [Div1]「CodePlus 2018 4 月赛」最短路 [Div1]「CodePlus 2018 4 月赛」Tommy 的结合

解题概况

这次我第一次参加Code++的比赛,然后自己傻傻的参加了Div1难度的,平时Codeforces比赛Div1难度没有这么高,所以这次有点蒙吧,这次比赛我做了不是很久,但是我还是想好好的做一下这套题目,一题一题做,好好写题解什么的,毒瘤题就跳过吧。 ......  查看更多