hyf

周冬《生成树的计数及其应用》

//----------------------------------------------------------------------------------------------------------------------------
排列
    1-n的一个排列i1、i2...in通过兑换变成标准排列1、2...n所需的对换次数和该排列逆序对个数奇偶性相同(一个排列中任意两个数对换后，逆序对奇偶性改变)
    记&(a1,a2..an)为(-1)的改排列奇偶性次幂
行列式
    那么一个方阵的行列式det A = ∑(1->n,i1->in) &(i1->in)*(ai1*ai2*...*ain)
    方阵的代数余子式Mij为方阵A去掉i行j列所有元素后的n-1阶方阵的有符号行列式(乘上-1的i+j次幂)
    方阵的主子式等于主对角线上任何一个坐标代数余子式的绝对值
    行列式等于它的任一行（列）的各元素与其代数余子式的乘积之和
    行列式一行（列）的元素等比例加到另一行（列）上，其行列式不变，故可化解方阵求行列式 O(n^3)
Matrix-Tree定理
    Kirchhoff矩阵C为G的度数矩阵(主对角线上填各点的度)减去G的邻接矩阵(故相连点ij则Cij=-1否则为0)
    图的生成树个数即为该图的kirchhoff矩阵的主子式的绝对值
//----------------------------------------------------------------------------------------------------------------------------

杨弋《Hash在信息学竞赛中的一类应用》

//----------------------------------------------------------------------------------------------------------------------------
例1.多维匹配
    基本思想是朴素+hash,用Rabin-Karp计算多维数组的hash值，相等的才值得朴素比较
    Rabin-Karp: f(s)=∑(i->len(s)) s[i]*p^(len(s)-i) mod q
例2.Equal squares
    和上题一样的hash,只是这里认为hash值相同那么举着那就相同了，这样一般出错率很小
    一个技巧是计算两个hash,一个用于确定hash表中的位置，另一个则用于比较
例3.不稳定匹配
    用数据结构维护hash值
总之就是利用Rabin-Karp的可递推性，利用各种数据结构的特点来快速计算hash值并进行维护。
//----------------------------------------------------------------------------------------------------------------------------

胡伯涛《最小割模型在信息学竞赛中的应用》

//----------------------------------------------------------------------------------------------------------------------------
引入
    首先介绍了网络流的基本知识和最大流最小割定理
    网络的最小割为求最大流后残留网络中与s连通的点集为S,其余为T
    最大流算法推荐sap
分数规划
    Min λ=a(x)/b(x) x∈S,b(x)>0
    则λ为f(x)=a(x)/b(x)的最小值
    令g(λ)=min{a(x)-λ*b(x)}
    g（λ）为严格递减函数 —— ①
    Dinkelbach定理λ为原规划的最小值当且仅当g(λ)=0 —— ②
    那么就可以根据①②来二分λ
    g(λ)=0 -> λ=λ*
    g(λ)<0 -> λ>λ*
    g(λ)>0 -> λ<λ*
应用
    例1.
    求一图的割集C, 使之平均边权最小
        λ=f(x)=∑(WeXe)/∑(Xe)=（WX）/X，若选边e则Xe=1，否则为0
        则g(λ)=min{(W-λ)X}
        二分λ,求g(λ)的方法是构新图，使We'=We-λ,则要求We'X,则新图的一个最小和割集，把所有负边选入后再最大流求最小割即可
    例2.
        图的一些定点权值已经给出，边权等于两端点权值的xor,求最小可能的边权和
        由于xor的每位可以单独考虑，所以问题转换为点权为{0,1}，两端点相同则边权为1，求最小边全和
        把原来所有无向边变成两条有向边，S到所有确定为0的点，所有确定为1的点连到T，求最小割即为答案，因为可以认为S割集全为0，T割集全为1
最大权闭合子图
    闭合子图指一子图的任意点后继都在图内的子图，可描述事件间必要条件的关系
    最大权闭合子图指最大点权和的闭合子图
    构造网络流： 原图中边均保留且容量为正无穷，所有正权点连到S,负权点连到T,容量为点权绝对值
                 证明原图的闭合子图V1与割[S,T]一一对应
                 最大权即为【正权和-最小割】
最大密度子图
    Maximize D=∑(Xe)/∑(Xv), Xe表e边是否存在，Xv表v点是否存在
    则令h(g)=max{∑Xe-∑gXv}, 求h(g)
    由于选择了边必须选择相应端点，所以初步算法是用最大权闭合子图解决
    改进的算法是使h(g)=min{∑gXv-∑Xe},而∑Xe=∑dVi/2-[V,V'],h(g)=min{∑gXv-∑dVi/2+[V,V']}意即最小割[V,V']，并且选择每个点V要付出代价,这个处理

可以把所有点连向T,容量即为权值，那么在割内的点还要割去权值的那条边，无误。
    若边带权，则把每个点的度数定义为齐所连边权值和
    若点带权，则把点权g换成(g-Pv)
二分图最小权覆盖集
    把原二分图每条变容量变为正无穷，从S向X和Y到T连容量为点权的边，最小割即可保证每条边都至少有一端在割集内
二分图最大权独立集
    总权值-最小权覆盖集
割的性质
    1.在给定网络中去掉割的边集则不存在从S到T的路径
    2.在给定的流网络中，任意一个割将点集划分成两部分
技巧
    1.用正无限容量排除不参与决策的边
    2.利用割的定义来分析最优性
    3.利用与源或汇关联的边容量处理点权
//----------------------------------------------------------------------------------------------------------------------------