容斥原理总结 概述: 先引入百度百科的定义: 在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算…
分类:ACM模板整理
欧拉函数,欧拉定理,费马小定理介绍及模板
欧拉函数总结 介绍 欧拉函数的定义:对于正整数n,欧拉函数是小于等于n的数中,与n互质的数的数目 欧拉函数又称 \phi 函数,例如\phi(8)=4,因为1,3,5,7均和8互质 定理: 如果n为某一个素数p,则:\p…
最近公共祖先LCA模板
概述 求最近公共祖先一共有3种算法: 离线Tarjan算法,复杂度为:O(n+q) 在线ST算法,把lca转换成rmq,复杂度为:O(NlogN) 在线倍增算法,利用二进制加速找的过程,复杂度:O(NlogN) 下面只写…
图的连通问题总结(Tarjan,求割点,求割边,点双联通分量,边双连通分量,缩点染色,强连通)
绪论 学习了一周图的连通性问题,现在总结一下关于图的连通性问题。图的连通性问题一般分为以下几种: 无向图求关节点(割点) 无向图求桥(割边) 无向图的点双连通分量 无向图的边双联通分量 有向图求强连通分量 还需要注意一些…
网络流的最大流,最小费用最大流,EK,Dinic,ISAP
相关总结更新啊在我的博客: 网络流相关算法总结,最大流EK算法,SAP算法,最小费用最大流,最小费用路算法,最大流最小割定理 最大流的EK算法和Dinic算法 EK算法 适用于点的数目比较稠密,点数比较小。 算法复杂度:…
匹配问题的相关概念,最小路径覆盖,点集覆盖,独立集,最大完备匹配KM算法,多重匹配
接上一篇文章,我介绍了二分图匹配的匈牙利算法,接下来继续说一说二分图的相关算法: 接下来就是一些干货了,模板: 权值最大完备匹配,KM算法 HDU2255 奔小康赚大钱(二分图的最大完备匹配,KM算法) 原理请从上面的链…
二分图配,染色法,匈牙利算法模板
匈牙利算法的本质是,不停地进行搜索找增广路,最后求出它的最大匹配. 以HDU2444为例,这道题先让判断是否是二分图,如果是求出它的最大匹配,那么就先用染色法,然后再用匈牙利算法 #include <bits/st…