青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風(fēng)寒，忽然年以殘，念往昔，語(yǔ)默心酸。二十光陰無(wú)一物，韶光賤，寐難安； 不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢(mèng)令

POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)

 關(guān)于LCA和RMQ問(wèn)題

一、最近公共祖先(Least Common Ancestors)

對(duì)于有根樹(shù)T的兩個(gè)結(jié)點(diǎn)u、v，最近公共祖先LCA(T,u,v)表示一個(gè)結(jié)點(diǎn)x，滿足x是u、v的祖先且x的深度盡可能大。另一種理解方式是把T理解為一個(gè)無(wú)向無(wú)環(huán)圖，而LCA(T,u,v)即u到v的最短路上深度最小的點(diǎn)。

這里給出一個(gè)LCA的例子：

例一

對(duì)于T=<V,E>
V={1,2,3,4,5}
E={(1,2),(1,3),(3,4),(3,5)}

則有：

LCA(T,5,2)=1
LCA(T,3,4)=3
LCA(T,4,5)=3

  
二、RMQ問(wèn)題(Range Minimum Query)

RMQ問(wèn)題是指：對(duì)于長(zhǎng)度為n的數(shù)列A，回答若干詢問(wèn)RMQ(A,i,j)(i,j<=n)，返回?cái)?shù)列A中下標(biāo)在[i,j]里的最小值下標(biāo)。這時(shí)一個(gè)RMQ問(wèn)題的例子：

例二

對(duì)數(shù)列：5,8,1,3,6,4,9,5,7 有：

RMQ(2,4)=3
RMQ(6,9)=6

RMQ問(wèn)題與LCA問(wèn)題的關(guān)系緊密，可以相互轉(zhuǎn)換，相應(yīng)的求解算法也有異曲同工之妙。

下面給出LCA問(wèn)題向RMQ問(wèn)題的轉(zhuǎn)化方法。

對(duì)樹(shù)進(jìn)行深度優(yōu)先遍歷，每當(dāng)“進(jìn)入”或回溯到某個(gè)結(jié)點(diǎn)時(shí)，將這個(gè)結(jié)點(diǎn)的深度存入數(shù)組E最后一位。同時(shí)記錄結(jié)點(diǎn)i在數(shù)組中第一次出現(xiàn)的位置(事實(shí)上就是進(jìn)入結(jié)點(diǎn)i時(shí)記錄的位置)，記做R[i]。如果結(jié)點(diǎn)E[i]的深度記做D[i]，易見(jiàn)，這時(shí)求LCA(T,u,v)，就等價(jià)于求E[RMQ(D,R[u],R[v])]，(R[u]<R[v])。例如，對(duì)于第一節(jié)的例一，求解步驟如下：

數(shù)列E[i]為：1,2,1,3,4,3,5,3,1
R[i]為：1,2,4,5,7
D[i]為：0,1,0,1,2,1,2,1,0

于是有：

LCA(T,5,2) = E[RMQ(D,R[2],R[5])] = E[RMQ(D,2,7)] = E[3] = 1
LCA(T,3,4) = E[RMQ(D,R[3],R[4])] = E[RMQ(D,4,5)] = E[4] = 3
LCA(T,4,5) = E[RMQ(D,R[4],R[5])] = E[RMQ(D,5,7)] = E[6] = 3

易知，轉(zhuǎn)化后得到的數(shù)列長(zhǎng)度為樹(shù)的結(jié)點(diǎn)數(shù)的兩倍加一，所以轉(zhuǎn)化后的RMQ問(wèn)題與LCA問(wèn)題的規(guī)模同次

 

數(shù)據(jù)很水，但是算法絕對(duì)經(jīng)典，題目要求兩個(gè)節(jié)點(diǎn)的最近公共祖先，這個(gè)tarjan算法使用了并查集+dfs的操作。這個(gè)算法研究了我兩個(gè)小時(shí)，開(kāi)始的時(shí)候在網(wǎng)上查找資料，寫(xiě)的都不盡人意，看不明白，后來(lái)干脆直接看代碼，模擬了一遍，搞懂了。。。看來(lái)計(jì)算機(jī)的世界，只有代碼才是王道！中間的那個(gè)并查集操作的作用，只是將已經(jīng)查找過(guò)的節(jié)點(diǎn)捆成一個(gè)集合然后再指向一個(gè)公共的祖先。另外，如果要查詢LCA(a,b)，必須把(a,b)和(b,a)都加入鄰接表。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
#define MAX 10001
int f[MAX];
int r[MAX];
int indegree[MAX];
int visit[MAX];
vector<int> hash[MAX],Qes[MAX];
int ancestor[MAX];


void init(int n)
{
    int i;
    for(i=1;i<=n;i++)
    {

        r[i]=1;
        f[i]=i;
        indegree[i]=0;
        visit[i]=0;
        ancestor[i]=0;
        hash[i].clear();
        Qes[i].clear();
    }

}


int find(int n)
{
    if(f[n]==n)
        return n;
    else
        f[n]=find(f[n]);
    return f[n];
}//查找函數(shù)，并壓縮路徑


int Union(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b)
        return 0;
    else if(r[a]<=r[b])
    {
        f[a]=b;
        r[b]+=r[a];
    }
    else
    {
        f[b]=a;
        r[a]+=r[b];
    }
    return 1;
    
}//合并函數(shù)，如果屬于同一分支則返回0，成功合并返回1


void LCA(int u)
{
    ancestor[u]=u;
    int i,size = hash[u].size();
    for(i=0;i<size;i++)
    {
        LCA(hash[u][i]);
        Union(u,hash[u][i]);
        ancestor[find(u)]=u;
    }
    visit[u]=1;
    size = Qes[u].size();
    for(i=0;i<size;i++)
    {
        if(visit[Qes[u][i]]==1)
        {
            printf("%d\n",ancestor[find(Qes[u][i])]);
            return;
        }
    }
}


int main()
{

    int testcase;
    int n;
    int i,j;
    scanf("%d",&testcase);
    for(i=1;i<=testcase;i++)
    {
        scanf("%d",&n);
        init(n);
        int s,t;
        for(j=1;j<=n-1;j++)
        {

            scanf("%d%d",&s,&t);
            hash[s].push_back(t);
            indegree[t]++;
        }
        scanf("%d%d",&s,&t);
        Qes[s].push_back(t);
        Qes[t].push_back(s);
        for(j=1;j<=n;j++)
        {
            if(indegree[j]==0)
            {
                LCA(j);
                break;
            }
        }
    }
    return 0;
}


不過(guò)可能是用了vector的關(guān)系，耗時(shí)47MS,也許改成單純的鏈表要更好些；
還有就是，如果這個(gè)樹(shù)的根節(jié)點(diǎn)不確定，邊沒(méi)有方向可言的話，又應(yīng)該如何做呢？（找不到根了。。。）
如果要找兩個(gè)節(jié)點(diǎn)之間的一條通路 又該怎么辦？
看來(lái)，這個(gè)問(wèn)題還有繼續(xù)研究下去的必要。。。

———————————————————————傳說(shuō)中的分割線——————————————————————————
指針版：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
#define MAX 10001

struct node
{

    int a;
    node *next;
}hash[MAX];
node Qes[MAX];

void Add(node hash[],int a,int b)
{

    node *p=&hash[a];
    node *q=p->next;

    node *r=new node;
    r->a=b;
    p->next=r;
    r->next=q;

}
int f[MAX];
int r[MAX];
int indegree[MAX];
int visit[MAX];
int ancestor[MAX];


void init(int n)
{
    int i;
    for(i=1;i<=n;i++)
    {

        r[i]=1;
        f[i]=i;
        indegree[i]=0;
        visit[i]=0;
        ancestor[i]=0;
        hash[i].next=NULL;
        Qes[i].next=NULL;
    }

}


int find(int n)
{
    if(f[n]==n)
        return n;
    else
        f[n]=find(f[n]);
    return f[n];
}//查找函數(shù)，并壓縮路徑


int Union(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b)
        return 0;
    else if(r[a]<=r[b])
    {
        f[a]=b;
        r[b]+=r[a];
    }
    else
    {
        f[b]=a;
        r[a]+=r[b];
    }
    return 1;
    
}//合并函數(shù)，如果屬于同一分支則返回0，成功合并返回1


void LCA(int u)
{
    ancestor[u]=u;
    node *p;
    for(p=hash[u].next;p!=NULL;p=p->next)
    {
        LCA(p->a);
        Union(u,p->a);
        ancestor[find(u)]=u;
    }
    visit[u]=1;
    for(p=Qes[u].next;p!=NULL;p=p->next)
    {
        if(visit[p->a]==1)
        {
            printf("%d\n",ancestor[find(p->a)]);
            return;
        }
    }
}


int main()
{

    int testcase;
    int n;
    int i,j;
    scanf("%d",&testcase);
    for(i=1;i<=testcase;i++)
    {
        scanf("%d",&n);
        init(n);
        int s,t;
        for(j=1;j<=n-1;j++)
        {

            scanf("%d%d",&s,&t);
            Add(hash,s,t);
            indegree[t]++;
        }
        scanf("%d%d",&s,&t);
        Add(Qes,s,t);
        Add(Qes,t,s);
        for(j=1;j<=n;j++)
        {
            if(indegree[j]==0)
            {
                LCA(j);
                break;
            }
        }
    }
    return 0;
}

汗，寫(xiě)了個(gè)指針版運(yùn)行速度居然比vector還慢，太打擊我對(duì)指針的信心了。。。可能是數(shù)據(jù)太弱了吧，指針的優(yōu)勢(shì)沒(méi)有發(fā)揮出來(lái)。。。


——————————————————傳說(shuō)中的分割線——————————————————————————————————
終于用RMQ過(guò)了，起初一直RE,原來(lái)是RM Q里面的數(shù)組開(kāi)小了。。。不過(guò)感覺(jué)時(shí)間效率不是很高，110MS，應(yīng)該是詢問(wèn)的次數(shù)太少的原因吧。
RMQ應(yīng)付的應(yīng)該是詢問(wèn)次數(shù)非常巨大的情況。而且它是在線的算法，可以按順序輸出結(jié)果，這樣才能AC題目啊。

 

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
vector<int>hash[10001];//用vector代替鄰接表

#define MAXN   10001
#define mmin(seq, a, b)  ((seq[a] < seq[b]) ? (a) : (b))
int indegree[MAXN];
/**///// DP status
int fij[100000][100];

template <typename T>
void st(T seq[], int n)//預(yù)處理
{ 
    memset(fij, 0, 100 * MAXN * sizeof(int));
    int k = (int)(log((double)n) / log(2.0)); 
    /**/////初始狀態(tài)
    for(int i = 0; i < n; i++)
        fij[i][0] = i; 
    /**/////遞推計(jì)算狀態(tài)
    for(int j = 1; j <= k; j++)
    {
        for(int i = 0; i + (1 << j) - 1 < n; i++)
        {
            //
            int m = i + (1 << (j - 1)); 
            //fij[i][j] = seq[fij[i][j - 1]] < seq[fij[m][j - 1]] ? fij[i][j - 1] : fij[m][j - 1];
            fij[i][j] = mmin(seq, fij[i][j - 1], fij[m][j - 1]);
        }
    }
}
template <typename T>
int RMQ(T seq[], int i, int j)//求解RMQ
{
    /**///// 用對(duì)2去對(duì)數(shù)的方法求出k
    int k = (int)(log(double(j - i + 1)) / log(2.0)); 
    /**/////
    //int t = seq[fij[i][k]] < seq[fij[j - (1 << k) + 1][k]] ? fij[i][k] : fij[j - (1 << k) + 1][k];
    int t = mmin(seq, fij[i][k], fij[j - (1 << k) + 1][k]);
    return t;
}

int E[MAXN*2+1];
int R[MAXN*2+1];
int D[MAXN*2+1];
int p=0;
void dfs(int r,int deep)//深搜，算出E,R,D數(shù)組
{
    p++;
    E[p]=r;
    D[p]=deep;
    R[r]=p;
    int i;
    int size=hash[r].size();
    for(i=0;i<size;i++)
    {

        dfs(hash[r][i],deep+1);
        p++;
        E[p]=r;
        D[p]=deep;
    }
    
}

int main()
{

    int testcase;
    int n;
    int i,j;
    int s,t;
    scanf("%d",&testcase);
    for(i=1;i<=testcase;i++)
    {
    
        scanf("%d",&n);
        for(j=1;j<=n;j++)
        {
            indegree[j]=0;
            hash[j].clear();
        }
        p=0;
            
        for(j=1;j<n;j++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            hash[a].push_back(b);
            indegree[b]++;
        }
        scanf("%d%d",&s,&t);
        int root;
        for(j=1;j<=n;j++)
        {

            if(indegree[j]==0)
            {
                root=j;
                break;
            }
        }
        dfs(root,0);
        st(D,2*n+2);
        if(R[s]<R[t])
            printf("%d\n",E[  RMQ(D,R[s],R[t]) ] );
        else
            printf("%d\n",E[ RMQ(D,R[t],R[s]) ] );

    }
    return 0;
}


 

posted on 2009-09-21 22:24 abilitytao 閱讀(3567) 評(píng)論(1)  編輯 收藏 引用

評(píng)論

# re: POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)[未登錄](méi) 2009-09-22 16:08 vincent

神牛平均一天切幾題啊..速度很汗顏啊  回復(fù)  更多評(píng)論   


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <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>
            
日韩视频在线免费观看|
一区二区三区产品免费精品久久75|
香蕉久久国产|
亚洲综合视频网|
亚洲欧美韩国|
欧美在线日韩|
欧美91大片|
欧美久久在线|
国产精品久久综合|
国产亚洲一级|
亚洲精华国产欧美|
91久久精品美女高潮|
久久成人这里只有精品|
欧美亚洲免费|
免费h精品视频在线播放|
老司机免费视频久久|
亚洲国产精品一区二区三区|
欧美黑人在线观看|
日韩午夜高潮|
久久国产精品久久久久久|
欧美阿v一级看视频|
国产精品成人一区二区网站软件|
国内精品久久久久久久影视麻豆
|
老鸭窝毛片一区二区三区|
亚洲国产裸拍裸体视频在线观看乱了中文|
亚洲精品日韩综合观看成人91|
在线一区免费观看|
欧美xart系列高清|
国产一级一区二区|
在线天堂一区av电影|
美女尤物久久精品|
亚洲专区国产精品|
欧美日韩国产天堂|
亚洲精品久久视频|
欧美ed2k|
欧美在线高清视频|
国产精品网红福利|
一区二区高清视频|
欧美不卡一区|
久久久精品日韩欧美|
国产精品一区二区久激情瑜伽|
日韩视频一区二区三区|
麻豆精品精华液|
性色一区二区三区|
国产精品制服诱惑|
亚洲一区二区三区高清|
亚洲激情视频网|
麻豆av一区二区三区|
在线观看91精品国产入口|
欧美一区在线视频|
亚洲特级毛片|
国产精品免费区二区三区观看|
亚洲精选久久|
久久这里只有|
久久精品国产99|
国产日韩欧美一区|
久久精品国产99国产精品澳门|
在线视频中文亚洲|
欧美日韩久久久久久|
亚洲精品久久在线|
亚洲国产小视频在线观看|
久久国产一二区|
国产一区二区在线观看免费|
性欧美大战久久久久久久久|
日韩天堂在线视频|
国产日产亚洲精品|
久久久www成人免费无遮挡大片|
欧美日韩国产精品一卡|
在线欧美日韩国产|
久久国产天堂福利天堂|
亚洲一区日韩在线|
国产日韩精品入口|
久久视频精品在线|
欧美一区二区私人影院日本|
黄色成人免费网站|
亚洲国产日韩欧美|
欧美日韩中文在线|
欧美亚洲综合在线|
久久久久久久性|
日韩特黄影片|
亚洲欧美日韩第一区|
永久免费精品影视网站|
亚洲国产精品t66y|
国产精品久久久久久久久婷婷|
久久9热精品视频|
久久伊人一区二区|
亚洲精品中文字幕在线观看|
一区二区三区欧美在线观看|
国产亚洲第一区|
亚洲福利精品|
欧美午夜剧场|
久久综合一区|
欧美日韩精品福利|
久久精品国产亚洲5555|
美女视频黄免费的久久|
一区二区欧美在线观看|
香蕉乱码成人久久天堂爱免费|
亚洲成色www8888|
一区二区高清视频在线观看|
国产色产综合产在线视频|
男人的天堂亚洲在线|
国产精品地址|
欧美阿v一级看视频|
欧美三级黄美女|
免费在线观看精品|
国产精品日韩高清|
亚洲国产天堂久久国产91|
国产精品爽爽ⅴa在线观看|
欧美国产欧美亚洲国产日韩mv天天看完整|
欧美三级欧美一级|
欧美国产在线视频|
国产日韩欧美在线视频观看|
亚洲经典在线|
国外成人在线|
亚洲制服少妇|
亚洲资源在线观看|
欧美日本免费|
亚洲国产日韩欧美在线99|
国语精品中文字幕|
午夜日韩视频|
欧美一级淫片播放口|
欧美日韩另类视频|
最近中文字幕mv在线一区二区三区四区|
国产午夜精品理论片a级大结局|
日韩一区二区免费看|
99国产精品国产精品久久|
麻豆精品在线观看|
欧美高清不卡在线|
亚洲国产女人aaa毛片在线|
欧美中文在线观看国产|
国产亚洲一区二区三区在线观看|
亚洲精品中文字幕在线|
亚洲国产日韩美|
免费h精品视频在线播放|
蜜臀av性久久久久蜜臀aⅴ四虎|
国产一区二区三区在线观看网站
|
欧美激情区在线播放|
在线免费观看日本欧美|
久久九九全国免费精品观看|
久久成人免费电影|
国产综合色一区二区三区|
欧美一区二区啪啪|
久久全球大尺度高清视频|
精品51国产黑色丝袜高跟鞋|
久久国产精品久久精品国产|
另类酷文…触手系列精品集v1小说|
欲香欲色天天天综合和网|
老牛国产精品一区的观看方式|
欧美成人a∨高清免费观看|
亚洲日本视频|
欧美日韩视频一区二区|
一区二区三区精品|
欧美一区在线视频|
在线观看视频一区|
欧美日本精品一区二区三区|
亚洲图色在线|
美国三级日本三级久久99|
亚洲国产小视频在线观看|
欧美精品自拍|
午夜精品久久久|
欧美国产高清|
亚洲免费影视第一页|
国产亚洲一级高清|
欧美紧缚bdsm在线视频|
亚洲一区尤物|
欧美激情精品久久久|
亚洲在线播放|
在线成人www免费观看视频|
欧美久久九九|
久久精品国产亚洲一区二区三区|
亚洲国产精品123|
亚洲欧美日韩爽爽影院|
在线观看日韩|
国产伦精品一区二区三区在线观看|
久久久精品国产免大香伊|
99精品国产在热久久婷婷|
久久亚洲综合色|
亚洲永久免费观看|
亚洲国产欧美一区|
国产亚洲毛片|
国产精品久久久久久模特|
老司机午夜精品视频|
亚洲一区三区电影在线观看|
亚洲国产精品久久久久秋霞蜜臀|
欧美一区二区|
一本色道婷婷久久欧美|
在线观看视频一区二区欧美日韩|
国产精品毛片高清在线完整版|
免费观看一级特黄欧美大片|
亚洲自拍偷拍麻豆|
99国产精品国产精品久久|
欧美寡妇偷汉性猛交|
久久久精品欧美丰满|
亚洲嫩草精品久久|
av不卡在线看|
一区二区激情视频|
亚洲伦理在线观看|
久久在线免费视频|
亚洲国产网站|
一区二区三区在线视频免费观看|