題目描述

?給定一個(gè) n個(gè)點(diǎn) m 條邊有向圖，每個(gè)點(diǎn)有一個(gè)權(quán)值，求一條路徑，使路徑經(jīng)過的點(diǎn)權(quán)值之和最大。你只需要求出這個(gè)權(quán)值和。

允許多次經(jīng)過一條邊或者一個(gè)點(diǎn)，但是，重復(fù)經(jīng)過的點(diǎn)，權(quán)值只計(jì)算一次。

輸入格式

第一行兩個(gè)正整數(shù) n,,m

第二行 n 個(gè)整數(shù)，依次代表點(diǎn)權(quán)

第三至 v 的有向邊。?

輸出格式

共一行，最大的點(diǎn)權(quán)之和。

題目鏈接:https://www.luogu.com.cn/problem/P3387

?

分析:

相信大家已經(jīng)看過題目了,在看我的題解之前也應(yīng)該看過別的大佬的題解了(畢竟我是蒟蒻),雖然所有的題解一上來就會(huì)明確告訴你思路是tarjan+拓?fù)?dp,但為什么是這個(gè)思路確很少分析,我們不妨來分析一下加深自己的理解。

對(duì)于這道題,要找出加權(quán)有向圖中一條路徑上最大的權(quán)值和sum(w),w我們第一時(shí)間想到是什么情況下sum(w)最大,第一反應(yīng)是路徑越長(zhǎng)則sum(w)趨于越大,雖然極其的不嚴(yán)格,但卻好比一根團(tuán)繩子(一個(gè)圖),表面上很難看出來哪一根最長(zhǎng),因?yàn)橛姓郫B起來的部分(環(huán)),所以第一步要拆折疊為直線(tarjan縮點(diǎn)),在縮點(diǎn)后,有向圖中的環(huán)消失,原圖中的環(huán)被縮成了點(diǎn)。

好,現(xiàn)在折疊的部分被拆開了,圖現(xiàn)在變成了有向無環(huán)圖,路徑清晰明確,是時(shí)候進(jìn)行dp了,用dp來找出最優(yōu)解(類似于最長(zhǎng)上升子序列,在選與不選中抉擇),但是想要進(jìn)行dp,還要滿足以下兩個(gè)條件:

1.最優(yōu)子結(jié)構(gòu)。

2.無后效性。

對(duì)于最優(yōu)子結(jié)構(gòu):我們規(guī)定,dp[i]為當(dāng)dp到點(diǎn)i時(shí)的最優(yōu)情況,那么dp[n]為最終的唯一解,設(shè)最后一次選取在點(diǎn)u->n之間,那么,要是dp[n]最大,有dp[n]=max(dp[n],dp[u]+w[n]);

證明:假設(shè)dp[u]不符合最優(yōu)解,那么則必定存在有dp1[u]>dp[u],那么有dp1[n]=dp1[u]+w[v]>dp[u],這與dp[n]的最優(yōu)性矛盾,因?yàn)樵趎時(shí)的dp[n]已經(jīng)是唯一最優(yōu)解。

然而對(duì)于無后效性,在某次dp時(shí)因?yàn)閐p此時(shí)的圖并不是嚴(yán)格線性的,合并前的狀態(tài)有可能影響合并后的走向,比如遇到多出度的點(diǎn),無法保證無后效性。

那么這時(shí)就要用到拓?fù)渑判?我個(gè)人的理解為,將一個(gè)有向無環(huán)圖變?yōu)橐粋€(gè)線性序列,在這個(gè)線性序列中,取任意兩點(diǎn)u,v,如果從u->v出現(xiàn)在縮點(diǎn)后圖的傳遞閉包中,那么在隊(duì)列中u必然在v之前。

這時(shí),dp變成了線性dp,無后效性輕松保證。

?

具體的算法實(shí)現(xiàn)

好,現(xiàn)在我們知道為什么要用這三樣?xùn)|西了,思路就變得清晰起來.首先對(duì)于tarjan,如果是從受歡迎的?；蛘邚钠渌麖?qiáng)連通分量的題過來的小伙伴應(yīng)該大致有一些了解。

在tarjan的過程中主要是動(dòng)態(tài)的更新兩個(gè)東西,dfn和low,代表著按時(shí)間上遍歷到的順序情況和夠追溯到的最早的棧中節(jié)點(diǎn)的次序號(hào),當(dāng)dfn[u]==low[u]時(shí),即某一次dfn時(shí)又指回了low[u],所以可以成環(huán)。

對(duì)于拓?fù)渑判蛭乙话銓慴fs(其他方法記不住,因?yàn)楸容^菜),具體思路為,找入度為0的點(diǎn)加入隊(duì)列,然后刪除該點(diǎn)的所有出度邊,在次尋找,重復(fù)下去直至空?qǐng)D,類似于dijkstra,只不過這里找的是路徑最大權(quán)值和。

那么廢話就不多說了,上碼。

感興趣的話可以關(guān)注微信公眾號(hào)：算法雜記，有相關(guān)問題可找我咨詢，同時(shí)可領(lǐng)取相關(guān)算法學(xué)習(xí)路線及資料，讓我們一起來學(xué)算法吧。