P1137 旅行計(jì)劃

題目地址

這是一道圖的題目
單向圖 并且沒(méi)有環(huán)(只能向西走 保證了沒(méi)有環(huán))
這題目要求計(jì)算出每個(gè)節(jié)點(diǎn)離最東邊點(diǎn)的最長(zhǎng)路徑
用拓?fù)渑判?完成對(duì)圖的遍歷
在遍歷過(guò)程完成dp 得到結(jié)果

拓?fù)渑判虻牧鞒?br> 先計(jì)算每個(gè)點(diǎn)的入度
然后將入度為0的點(diǎn)寫入隊(duì)列
然后開(kāi)始遍歷入度為0的點(diǎn)
刪除入度為0的點(diǎn) 將與入度為0點(diǎn)的子節(jié)點(diǎn)入度-1
然后將新得到得入度為0得點(diǎn)重新寫入隊(duì)列
繼續(xù)上面得遍歷過(guò)程 直到所有的點(diǎn)入度為0

dp的過(guò)程
用數(shù)組result保存每個(gè)點(diǎn)的結(jié)果
第一批入度為0的點(diǎn)賦值為1
result[i]=max(result[父節(jié)點(diǎn)])+1


#include <stdio.h>

//圖的邊的結(jié)構(gòu)體(也可以用來(lái)表示樹(shù))
struct LinkList
{
    //節(jié)點(diǎn)編號(hào)
    int index;
    //所有連接節(jié)點(diǎn)的邊 包括根節(jié)點(diǎn)
    LinkList* next;
    // LinkList* pre;
};

void deleteLinkList(LinkList* l)
{
    LinkList* next=l;
    while (next!=NULL)
    {
        LinkList* now=next->next;
        delete next;
        next=now;
    }
}


//添加單項(xiàng)邊
void addSinglEv(LinkList** ev,int start,int end)
{
    LinkList* l=new LinkList;
    l->index=end;

    if(ev[start]==NULL)
    {
        l->next=NULL;
        ev[start]=l;
    }
    else{
        l->next=ev[start];
        ev[start]=l;
    }
}

struct Queue
{
    int start; //隊(duì)列起點(diǎn)
    int end;   //隊(duì)列終點(diǎn)
    int maxLen;//隊(duì)列最大元素個(gè)數(shù)
    int* data;//隊(duì)列元素
};

Queue* newQueue(int maxLen)
{
    Queue* q=new Queue;
    q->maxLen=maxLen;
    q->data=new int[maxLen];
    q->start=0;
    q->end=0;
    return q;
}

void deleteQueue(Queue* q)
{
    delete q->data;
    delete q;
}

//入隊(duì)
void inqueue(Queue* q,int num){
    q->data[q->end]=num;
    q->end++;
    if(q->end>=q->maxLen)
    {
        q->end=0;
    }
}

//出隊(duì)
int dequeen(Queue* q){
    int num=q->data[q->start];
    q->start++;
    if(q->start>=q->maxLen)
    {
        q->start=0;
    }
    return num;
}

//隊(duì)列元素多少
int sizeOfQueue(Queue* q)
{
    if(q->start==q->end)
    {
        return 0;
    }
    else{
        int len=q->end-q->start;
        if(len>0)
        {
            return len;
        }
        else{
            return len+q->maxLen;
        }
    }
}

//隊(duì)列是否為空
int isEmpQueue(Queue* q)
{
    return q->start==q->end;
}


int main(){
    int n,m;
    int i,j;
    scanf("%d %d",&n,&m);
    int* result=new int[n];

    //儲(chǔ)存節(jié)點(diǎn)入度
    int* input=new int[n];
    //記錄樹(shù)所有頂點(diǎn)
    LinkList** ev=new LinkList*[n];

    for(i=0;i<n;i++)
    {
        input[i]=0;
        result[i]=0;
        ev[i]=NULL;
    }

    int tmp1,tmp2;
    for(i=0;i<m;i++)
    {
        scanf("%d %d",&tmp1,&tmp2);
        tmp1--;
        tmp2--;

        //添加單向邊
        addSinglEv(ev,tmp1,tmp2);
        //入度+1
        input[tmp2]++;
    }

    Queue* q=newQueue(m);
    for(i=0;i<n;i++)
    {
        if(input[i]==0)
        {
            inqueue(q,i);
            result[i]=1;
            input[i]=-1;
        }
    }

    while (!isEmpQueue(q))
    {
        int size=sizeOfQueue(q);
        for(i=0;i<size;i++)
        {   
            //刪除入度為0的節(jié)點(diǎn)
            int index=dequeen(q);
            int value=result[index]+1;
            LinkList* l=ev[index];
            //遍歷子節(jié)點(diǎn)
            while (l!=NULL)
            {
                int newIndex=l->index;
                //計(jì)算子節(jié)點(diǎn)的值
                if(result[newIndex]<value)
                {
                    result[newIndex]=value;
                }

                //子節(jié)點(diǎn)入度-1
                input[newIndex]--;
                //將入度為0的點(diǎn)入隊(duì) 作為下一批的遍歷對(duì)象
                if(input[newIndex]==0)
                {
                    inqueue(q,newIndex);
                    input[newIndex]=-1;
                } 
                l=l->next;
            }
        }
    }
    

    for(i=0;i<n;i++)
    {
        deleteLinkList(ev[i]);
    }
    delete ev;

    deleteQueue(q);

    for(i=0;i<n;i++)
    {
        printf("%d\n",result[i]);
    }
    delete input;
    delete result;
}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市褂乍,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌帚称,老刑警劉巖鲜锚,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件刽宪,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡撩满,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門绅你,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)伺帘,“玉大人,你說(shuō)我怎么就攤上這事忌锯∥奔蓿” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵汉规,是天一觀的道長(zhǎng)礼殊。 經(jīng)常有香客問(wèn)我,道長(zhǎng)针史,這世上最難降的妖魔是什么晶伦? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮啄枕,結(jié)果婚禮上婚陪,老公的妹妹穿的比我還像新娘。我一直安慰自己频祝,他們只是感情好泌参,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著常空,像睡著了一般沽一。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上漓糙,一...
    開(kāi)封第一講書(shū)人閱讀 52,713評(píng)論 1 312
  • 那天铣缠,我揣著相機(jī)與錄音,去河邊找鬼昆禽。 笑死蝗蛙,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的醉鳖。 我是一名探鬼主播捡硅,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼盗棵!你這毒婦竟也來(lái)了壮韭?” 一聲冷哼從身側(cè)響起北发,我...
    開(kāi)封第一講書(shū)人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎泰涂,沒(méi)想到半個(gè)月后鲫竞,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡逼蒙,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年从绘,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片是牢。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡僵井,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出驳棱,到底是詐尸還是另有隱情批什,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布社搅,位于F島的核電站驻债,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏形葬。R本人自食惡果不足惜合呐,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望笙以。 院中可真熱鬧淌实,春花似錦、人聲如沸猖腕。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)倘感。三九已至放坏,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間老玛,已是汗流浹背轻姿。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留逻炊,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓犁享,卻偏偏與公主長(zhǎng)得像余素,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子炊昆,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容