Posted on 2009-09-17 18:13
hyf 阅读(681)
评论(0) 编辑 收藏 引用 所属分类:
OI
周冬《生成树的计数及其应用》
//----------------------------------------------------------------------------------------------------------------------------
排列
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.利用与源或汇关联的边容量处理点权
//----------------------------------------------------------------------------------------------------------------------------