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.利用與源或匯關聯的邊容量處理點權
//----------------------------------------------------------------------------------------------------------------------------