『OI笔记』次小生成树
前置芝士 一点点图论芝士 Kruskal(或者你用Prim也行),用来求最小生成树 定义 定义就是字面意思,无需解释。 思路 先将输入的图的最小生成树求出来,再枚举没有增加过的边,将他们加入到最小生成树当中去。新增一条边之后,我们就可以得到一个…
592 2021-09-26 0 康一康『OI笔记』插头DP
前言 好家伙,木板题都是黑题,这东西还要不要学了?(好吧还是要的。) 正文 定义 插头 首先,我们定义插头这个概念。如图: 对于这个图,在格子[1,1]中,我们说这有一个下插头,在格子[2,1]中,我们说这里有一个上插头。 轮廓线 如图: 对于图中黄色…
627 2021-09-09 0 康一康