ACM模板整理

分类:ACM模板整理

ACM模板整理

图的连通问题总结(Tarjan,求割点,求割边,点双联通分量,边双连通分量,缩点染色,强连通)

绪论 学习了一周图的连通性问题,现在总结一下关于图的连通性问题。图的连通性问题一般分为以下几种: 无向图求关节点(割点) 无向图求桥(割边) 无向图的点双连通分量 无向图的边双联通分量 有向图求强连通分量 还需要注意一些…

ACM模板整理

匹配问题的相关概念,最小路径覆盖,点集覆盖,独立集,最大完备匹配KM算法,多重匹配

接上一篇文章,我介绍了二分图匹配的匈牙利算法,接下来继续说一说二分图的相关算法: 接下来就是一些干货了,模板: 权值最大完备匹配,KM算法 HDU2255 奔小康赚大钱(二分图的最大完备匹配,KM算法) 原理请从上面的链…