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

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>
            
国产精品久久久久久久7电影|
久久青草欧美一区二区三区|
欧美日韩中文|
亚洲尤物影院|
亚洲欧美日韩网|
激情欧美一区二区三区|
欧美国产精品久久|
欧美日韩一级大片网址|
午夜在线一区|
久久久久一区二区三区|
亚洲精品日韩综合观看成人91|
亚洲精品国产欧美|
国产精品成人播放|
免费不卡在线观看|
欧美日韩三级|
久久婷婷国产综合精品青草|
欧美a级大片|
性欧美videos另类喷潮|
久久午夜国产精品|
亚洲欧美日韩在线播放|
久久频这里精品99香蕉|
亚洲欧美日韩精品久久亚洲区|
欧美一区二区三区在线免费观看|
亚洲欧洲日产国产综合网|
亚洲综合视频在线|
亚洲欧洲日本国产|
久久成人精品|
亚洲永久免费av|
欧美成人一区二区三区|
欧美伊人久久久久久午夜久久久久
|
欧美在线看片|
91久久国产综合久久91精品网站|
日韩亚洲欧美一区|
亚洲国产高清视频|
亚洲综合色激情五月|
日韩一级大片|
久久久免费av|
久久精品国产免费看久久精品|
欧美bbbxxxxx|
麻豆av福利av久久av|
国产精品视频xxx|
日韩亚洲精品在线|
亚洲精品资源|
老司机久久99久久精品播放免费
|
99国产精品视频免费观看|
在线观看欧美日韩|
欧美在线观看日本一区|
性做久久久久久免费观看欧美|
欧美日韩精品一区二区三区|
另类综合日韩欧美亚洲|
国产一区二区日韩精品欧美精品|
99一区二区|
亚洲图片在线|
欧美视频一区二区三区|
夜夜躁日日躁狠狠久久88av|
亚洲精品欧美精品|
欧美成人在线网站|
欧美激情综合色|
亚洲精品国产日韩|
欧美国产综合视频|
亚洲精品乱码久久久久久蜜桃91|
在线免费观看日韩欧美|
久久人人爽爽爽人久久久|
久久艳片www.17c.com|
影音先锋中文字幕一区|
久久久久久国产精品mv|
欧美岛国激情|
亚洲人线精品午夜|
欧美日韩一区不卡|
99精品久久|
午夜免费电影一区在线观看|
国产精品亚洲美女av网站|
性做久久久久久久免费看|
久久xxxx|
亚洲国产婷婷香蕉久久久久久99
|
亚洲视频香蕉人妖|
欧美在线免费|
在线国产日韩|
欧美精品入口|
亚洲已满18点击进入久久|
久久久久久色|
亚洲日本中文|
国产精品女人毛片|
久久精品亚洲热|
亚洲看片网站|
久久成人人人人精品欧|
亚洲电影激情视频网站|
国产精品av久久久久久麻豆网|
亚洲图片在线|
国产精品久久久久久久久久妞妞
|
亚洲国产一区二区视频|
亚洲深夜福利网站|
国内精品久久久久久影视8|
欧美va日韩va|
午夜日韩在线观看|
最新69国产成人精品视频免费
|
国产综合久久久久久|
蜜桃av综合|
亚洲在线电影|
亚洲国产欧美日韩精品|
午夜在线不卡|
亚洲伦理在线|
国内伊人久久久久久网站视频|
欧美成人精品在线播放|
性欧美长视频|
avtt综合网|
欧美va亚洲va日韩∨a综合色|
亚洲字幕在线观看|
亚洲精品免费一二三区|
国产女主播一区二区|
欧美久久久久免费|
久久久亚洲精品一区二区三区|
av成人天堂|
亚洲国产精品一区二区www|
久久gogo国模裸体人体|
亚洲午夜精品一区二区|
亚洲高清视频的网址|
国产情人节一区|
欧美视频四区|
欧美日韩另类综合|
欧美激情片在线观看|
久久免费高清|
久久久久国色av免费观看性色|
亚洲欧美一区二区三区极速播放|
av成人动漫|
亚洲精品在线一区二区|
亚洲第一精品福利|
欧美成人免费在线观看|
久久久夜精品|
久久人人97超碰国产公开结果
|
亚洲国产精品久久久久久女王|
久久综合九色欧美综合狠狠|
久久久综合精品|
欧美在线观看一二区|
欧美一区二区三区免费观看视频|
国产精品99久久不卡二区|
99精品视频免费|
99re在线精品|
国产精品99久久久久久有的能看|
亚洲三级影片|
日韩一区二区免费看|
99精品国产热久久91蜜凸|
夜夜嗨av一区二区三区网站四季av|
亚洲国产精品尤物yw在线观看|
亚洲国产老妈|
亚洲另类一区二区|
中文在线资源观看视频网站免费不卡|
亚洲精品乱码久久久久久日本蜜臀|
最近中文字幕日韩精品|
日韩视频一区二区三区在线播放|
亚洲人成小说网站色在线|
一本久道久久久|
亚洲在线不卡|
久久九九精品|
亚洲电影免费在线|
99精品热6080yy久久
|
最新国产乱人伦偷精品免费网站
|
国产精品区一区二区三区|
欧美日韩精品在线|
欧美日韩中文字幕精品|
欧美午夜激情在线|
国产欧美日韩综合精品二区|
国产一区二区黄色|
亚洲第一级黄色片|
99精品国产热久久91蜜凸|
午夜精品福利在线观看|
久久色在线播放|
亚洲黄一区二区|
亚洲欧美国产日韩天堂区|
久久麻豆一区二区|
欧美久久久久久|
国产手机视频精品|
亚洲精品看片|
久久久精品一区|
亚洲国产精品一区二区第一页|
在线综合视频|
能在线观看的日韩av|
国产精品福利影院|
亚洲国产日韩一级|
欧美一区二区在线播放|
亚洲二区在线观看|
欧美亚洲在线观看|
欧美日韩在线播放一区|
亚洲成在人线av|
亚洲欧美制服中文字幕|
亚洲第一福利在线观看|
先锋a资源在线看亚洲|
欧美日本亚洲|
亚洲第一二三四五区|
欧美一区二区私人影院日本|
欧美激情视频在线免费观看 欧美视频免费一
|
久久综合激情|
亚洲欧美日韩系列|
欧美日韩免费看|
亚洲韩国日本中文字幕|
久久免费的精品国产v∧|
亚洲视频一区二区|
欧美精品免费在线|
亚洲人体1000|
欧美jizz19hd性欧美|