• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 18,  comments - 5,  trackbacks - 0

            一、定義與定理
                  LCA:Least Common Ancestors(最近公共祖先),對于一棵有根樹T的任意兩個節點u,v,求出LCA(T, u, v),即離跟最遠的節點x,使得x同時是u和v的祖先。
                  在線算法:用比較長的時間做預處理,但是等信息充足以后每次回答詢問只需要用比較少的時間。
                  離線算法:先把所有的詢問讀入,然后一起把所有詢問回答完成。
                  RMQ:給出一個數組A,回答詢問RMQ(A, i, j),即A[i...j]之間的最值的下標。
            二、DFS+RMQ
                  1)Sparse Table(ST)算法
                  描述:

             1 //初始化
             2 INIT_RMQ
             3 //max[i][j]中存的是重j開始的i個數據中的最大值,最小值類似,num中存有數組的值
             4     for i : 1 to n
             5         max[0][i] = num[i]
             6     for i : 1 to log(n)/log(2)
             7         for j : 1 to n
             8             max[i][j] = MAX(max[i-1][j], max[i-1][j+2^(i-1)]
             9 //查詢
            10 RMQ(i, j)
            11     k = log(j-i+1/ log(2)
            12     return MAX(max[k][i], max[k][j-2^k+1])

                  分析:初始化過程實際上是一個動態規劃的思想。易知,初始化過程效率是O(nlogn),而查詢過程效率是O(1)。ST是一個在線算法。
                  示例:POJ 3368 解題報告
                  2)求解LCA問題
                  描述:
                  (1)DFS:從樹T的根開始,進行深度優先遍歷,并記錄下每次到達的頂點。第一個的結點是root(T),每經過一條邊都記錄它的端點。由于每條邊恰好經過2次,因此一共記錄了2n-1個結點,用E[1, ... , 2n-1]來表示。
                  (2)計算R:用R[i]表示E數組中第一個值為i的元素下標,即如果R[u] < R[v]時,DFS訪問的順序是E[R[u], R[u]+1, ..., R[v]]。雖然其中包含u的后代,但深度最小的還是u與v的公共祖先。
                  (3)RMQ:當R[u] ≥ R[v]時,LCA[T, u, v] = RMQ(L, R[v], R[u]);否則LCA[T, u, v] = RMQ(L, R[u], R[v]),計算RMQ。
                  由于RMQ中使用的ST算法是在線算法,所以這個算法也是在線算法。
                  示例:ZOJ 3195 解題報告
            三、Tarjan算法
                  描述:Tarjan算法是一個離線算法,也就是說只有先獲得所有的查詢,再按一個特定的順序進行運算。

             1 //parent為并查集,FIND為并查集的查找操作
             2 Tarjan(u)
             3     visit[u] = true
             4     for each (u, v) in QUERY
             5         if visit[v]
             6             ans(u, v) = FIND(v)
             7     for each (u, v) in TREE    
             8         if !visit[v]
             9             Tarjan(v)
            10             parent[v] = u
                  示例:HDOJ 2586 解題報告
            posted on 2009-07-04 15:25 Icyflame 閱讀(6965) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
            亚洲午夜福利精品久久| 国产精品成人精品久久久| 久久久久久国产精品无码下载| 国产一区二区久久久| 久久人爽人人爽人人片AV | 人妻少妇精品久久| 久久久久久国产精品美女 | 97精品国产97久久久久久免费| 久久99国产综合精品| 久久久久成人精品无码 | 一本久久综合亚洲鲁鲁五月天| 色综合久久中文字幕无码| 久久久久久久久久久免费精品| 久久久久久亚洲Av无码精品专口| 久久99精品久久久久久噜噜| 久久久久女人精品毛片| 久久精品视频一| 久久AⅤ人妻少妇嫩草影院| 久久国产精品久久久| 欧美黑人又粗又大久久久| 欧美精品国产综合久久| 欧美性猛交xxxx免费看久久久| 国产精品九九九久久九九| 久久精品国产亚洲AV不卡| 色8激情欧美成人久久综合电| 久久一日本道色综合久久| 午夜视频久久久久一区 | 久久精品国产亚洲Aⅴ香蕉| 91麻豆精品国产91久久久久久| 精品国产91久久久久久久 | 久久精品国产色蜜蜜麻豆 | 亚洲熟妇无码另类久久久| 久久人做人爽一区二区三区 | 久久无码av三级| 色综合久久综精品| 国产精品成人无码久久久久久| 香蕉久久夜色精品国产小说| 色综合久久中文色婷婷| 久久99精品久久久久久野外| 久久高清一级毛片| 久久综合视频网站|