差分约束系统学习笔记

发布于 2018-03-17

差分约束系统,就是给定一些 $ x_i – x_j >= d $ 的不等式,求出其中的一组解。我们可以转化为最短路来解决该类问题。


强连通分量

发布于 2018-03-17

概念 我们先来明确一些概念。 子图 图G=(V,E),G’=(V’,E’)中,若V’ ∈ V,E’ ∈ E,并且E’中的边所关联的 …


分层图最短路

发布于 2018-03-11

定义 分层图最短路问题,一般是指我们在可以进行分层的图上进行最短路。 一般模型是: 在图上,有k次机会可以直接通过一条边,问起点与 …