路径寻找问题（隐式图）
路径寻找问题（隐式图）
一些情况下，图不是事先给定，从输入中直接给出的，而是根据实际情况在程序中动态生成的，称为“隐式图”。
路径寻找问题主要是求从某个初状态到某个终状态的最优路径（关键是存在状态间的相互转移，所以可以把状态看作是图上的节点），一般可以转化为隐式图，然后利用图的遍历或者求图的最短路来求解。
例题
隐式图中最短路
CF1846G（把当前的患病状态作为图上的节点，结合每种药的药效用位运算来连边）
P1379（经典问题） uva10603 （注意图的生成方式）
uva1601
隐式图中最长路
uva437（经典矩形覆盖问题）
This post is licensed under CC BY 4.0 by the author.