容斥原理总结 概述： 先引入百度百科的定义: 在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算…
分类：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…