ioi2016集訓隊第一次作業(yè)題解

CBAL題目大給定一個N個點（從1到N標號）M條邊的有向圖。請你統(tǒng)計無序?qū)?XY(XY1X的路徑，和一條從點1到點Y的路徑，且兩條路徑除了點1以外沒有公共點。1≤n≤0≤m≤數(shù)據(jù)集1（30分）數(shù)據(jù)3（50分）算法分基本概要解決這個問題，先要了解幾對于一個有向圖，如果從給定的起點到某個節(jié)點X的所有路徑都經(jīng)過節(jié)點X的必經(jīng)點中離起點最遠（X最近）X的最近必經(jīng)點（immediatedominator），記idom[X]=Y。最近必經(jīng)點是唯一的。將除起點外所有節(jié)點與最近必經(jīng)點連接構(gòu)成一棵樹，稱為支配樹（DominatorTree。相乘并累加即是滿足條件的無序?qū)€數(shù)。因此本題的重點在于如何快速求出給定有向圖的支配樹。DAGG上的節(jié)點有嚴格的拓撲序，即只能從一個拓撲序靠前的點到達一個拓撲序靠后的點。在這種情況下，某個節(jié)點的最近必經(jīng)點一定是拓撲序更小的點，我們可以按照拓撲序增量構(gòu)造支配樹。1～X1的節(jié)點組成的支配樹，現(xiàn)在要加入節(jié)XX的節(jié)點，這些節(jié)點的最近公共祖先（LCA）就是節(jié)點X的最近必經(jīng)點，據(jù)此將節(jié)點X加入支配樹中。LCAO((NMlogN)30NMDFS，如果能到達某個節(jié)點，則被刪除的點不是這個節(jié)點的必經(jīng)點。忽略所有不可達點，時間復雜度O(NM)，能得到20分。結(jié)合DAG上的算法可以得到50分?？焖偎銓τ贜M比較大的圖，可以使用Lengauer-Tarjan算法計算Lengauer-Tarjan算法分為以下三個DFSDFS對于一個節(jié)點Y，存在祖先X能通過一系列節(jié)點pi（可以為0個）到達節(jié)點Y，且?i,dfi>dfn[Y]，稱節(jié)點X是節(jié)點Y的半必經(jīng)點（semidominator），記semi[YX半必經(jīng)點可以通過半必經(jīng)點定理計算。半必經(jīng)點定理描述對于一個節(jié)點Y，考慮所有能直接到達它的節(jié)點，設其中一個為dfn[Xdfn[Y]，此XZ，滿dfn[Z>dfn[Y時，semi[Z]為可能的半必經(jīng)點以上所有可能的節(jié)點中，DFS時間戳（dfn）最小的節(jié)點為Y的半必經(jīng)半必經(jīng)點不一定是必經(jīng)點，需要通過必經(jīng)點定理修正。必經(jīng)點定理描Xsemi[X的路徑上的其它節(jié)點，記其中半必經(jīng)點時間戳最小的節(jié)點為Z；semi[Z]=semi[X]idom[X]=semi[Z?=semi[X]idom[Xidom[Z]實注意到，在計算半必經(jīng)點的過程中如果某個節(jié)點的前驅(qū)結(jié)點的時間戳比它大，需要這個前驅(qū)結(jié)點的所有時間戳比當前考慮節(jié)點大的祖先。計算最近必經(jīng)點的過程中也要考慮它和半必經(jīng)點之間的路徑上的所有節(jié)點?？梢园凑諘r間戳逆序計算每個節(jié)點的半必經(jīng)點，此時所有時間戳更小的節(jié)點仍未計算，在考察時間戳大的祖先時可以直接它在已計算節(jié)點森林中的所有祖先。已計算節(jié)點森林可以用并查集來實現(xiàn)。在計算最近必經(jīng)點時，在某個節(jié)點剛被加入已計算節(jié)點森林時立即計算以它為半必經(jīng)點的所有節(jié)點的最近必經(jīng)點。O((NMlogN)1O(NM)，能得到本題所有算法相關(guān)Lengauer-Tarjan算法正確性的嚴謹證明，可見于“AFastForFindingDominatorsina1本題中并查集具有祖先關(guān)系，不能按秩合并。根據(jù)“Worst-CaseysisofSetUnionAlgo