一月 23, 2022

最小生成树

MST​ 设$N=(V,E)$是一个连通网，$U$是顶点集$V$的一个非空子集，边$(u,v)$是一个具有最...

十二月 08, 2021

图论复习(最短路)

前言​ 下学期开始讲数据结构，我自己比较想去争取一下免修。不过其实关于图论的部分基本上已经是忘得差不多了（我觉得我现在可能唯一还会的算法就是倍增...

九月 05, 2021

2-SAT问题

2-SAT问题描述有n个组，第i个组里有两个节点$A_i, A_i’$ 。需要从每个组中选出一个。而某些点不可以同时选出（称之为不相容）。任务是保证...

九月 05, 2021

二分图匹配

二分图的匹配二分图的最大匹配增广路一条匹配边与非匹配边交替出现的路径叫做增广路 匹配边：两个点已经处于已选集合里面的边 非匹配边：这条边有个点不属于已...