CF901C Bipartite Segments(二分图)

题目链接

CF

题意简述

定义一个“偶环”为边数为偶数的回路(回路又被称作“边简单环”,即不经过重复边且首尾点相同的途径)。

给你一张不含“偶环”的无向图。称一个区间是“好的”,当且仅当编号在这个区间中的点的导出子图是一张二分图。

多组询问,每次询问一个给定区间有多少个子区间是“好的”。

点数、边数、询问数均不超过 $3\cdot 10^5$ 。

「NOI2014」购票(斜率优化,点分治)

题目链接

UOJ

洛谷

题意简述

给你一棵树,$i$ 号点有 $p_i$、$q_i$ 和 $l_i$ 三个属性,每条边有给定的长度。

从一个点出发可以到达其祖先中与其距离不超过 $l_i$ 的点,费用为 $p_i\cdot dis+q_i$,求每个点到根的最小费用。

点数不超过 $2\cdot 10^5$ 。

悬崖边的踟蹰 —— CSP-S 2019

标题来自 三月のライオン Chapter.64 銀の羽根

答案只在漆黑的水底。

越是前进,下一个答案就只能在更深的地方找到。

以前越是潜入,就能获得答案。

比起恐怖,欲望更胜一筹。

但是成为职业棋手 6 年后,如今变得完全不能前进。

即便带着要撕碎全身的想法去潜入,但是却空手而回,已经是很常见的事了。

比起 「也许能找到」,「反正又不一定能找到」这个念头胜利的时候,就只能进行有限的努力了。

但是,桐山和二海堂无视了那样的我。

理所当然一样无论多少次都跳入其中。根本就不正常。

他们即便屡次空手而归,也会制定对策继续挑战。

丝毫不介意痛苦,无论多少次都投身其中。

只留下,被恐惧压倒的我。

基于 Capacity Scaling 的弱多项式复杂度最小费用流算法

大多数人所使用的费用流算法,即每次求出残量网络中 $s$ 到 $t$ 关于费用的最短路进行增广(将 Dinic 最大流算法中的 BFS 改为 SPFA),是伪多项式复杂度的,最坏情况下复杂度为 $O(nmf)$,其中 $f$ 为最大流。已知有一种在点数为 $n$,边数为 $O(n^2)$,值域为 $O(2^{n/2})$ 时将其用时卡成关于 $n$ 的指数级复杂度的构造方法。

本文将介绍一种复杂度为进行 $O(m\log U)$ 次($U$ 表示边的最大容量)无负权边单源最短路(使用 priority_queue 实现 Dijkstra 算法,总复杂度即为 $O(m^2\log U\log m)$)的弱多项式复杂度算法。

其实这个算法并不是很复杂(只是相关资料比较少,会对学习造成一定困难,这也是我写这篇博客的原因),最小费用最大流的模板也只需要 $2.5KB$,并不比常见的伪多项式复杂度算法长很多。