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

母函数总结 概述 母函数，又称生成函数，是ACM竞赛中经常使用的一种解题算法，常用来解决组合方面的题目。 母函数有两种，一种是指数型母函数一种是普通型母函数 普通型母函数 普通型母函数通常解决类似如下的问题： 给5张1元…

欧拉函数总结 介绍 欧拉函数的定义：对于正整数n，欧拉函数是小于等于n的数中，与n互质的数的数目 欧拉函数又称 \phi 函数，例如\phi(8)=4,因为1,3,5,7均和8互质 定理： 如果n为某一个素数p，则:\p…

概述 求最近公共祖先一共有3种算法： 离线Tarjan算法,复杂度为:O(n+q) 在线ST算法，把lca转换成rmq,复杂度为：O(NlogN) 在线倍增算法，利用二进制加速找的过程,复杂度:O(NlogN) 下面只写…

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

相关总结更新啊在我的博客: 网络流相关算法总结,最大流EK算法，SAP算法，最小费用最大流，最小费用路算法,最大流最小割定理 最大流的EK算法和Dinic算法 EK算法 适用于点的数目比较稠密，点数比较小。 算法复杂度:…

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

匈牙利算法的本质是，不停地进行搜索找增广路，最后求出它的最大匹配. 以HDU2444为例，这道题先让判断是否是二分图，如果是求出它的最大匹配，那么就先用染色法，然后再用匈牙利算法 #include <bits/st…

#include <bits/stdc++.h> using namespace std; const int N=5e5+20; struct dicTree { int next[N][26],fail[…

  直接上模板吧： 以NYOJ动物统计为例 #include <cstdio> #include <cstring> #include <string> #include &…