Description

8102年，Normalgod在GLaDOS的幫助下，研制出了傳送槍。但GLaDOS想把傳送槍據為己有，于是把Normalgod扔進了一間實驗室。這間實驗室是一棵有n個節點的樹。現在Normalgod在一號節點，出口也在一號節點，但為了打開它，必須經過每一個節點按下每個節點的開關，出口才能打開。GLaDOS為了殺死Normalgod，開始在實驗室里釋放毒氣，因此Normalgod必須盡快逃出這間實驗室。
? ? ? ? ? ??當然，Normalgod手中的傳送槍是可以使用的。傳送槍可以發射出兩個顏色不同的傳送門。Normalgod可以從其中一個傳送到另一個。盡管傳送槍可以在視野范圍內的任何一個經過特殊處理的表面打開一扇傳送門，但這間實驗室的設計使得Normalgod只能在他所處的房間內打開一個傳送門。 在已經存在了一個同顏色的傳送門時，打開新的傳送門會使與它同顏色的舊門消失。傳送和打開傳送門所需時間為0。
? ? ? ? ? ? ?顯然，利用傳送槍會讓Normalgod更快解決謎題，可Normalgod死在了按下最后一個按鈕的路上。盡管如此，GLaDOS還是很想知道到底Normalgod最快能用多久逃出去，這對她的實驗室設計方法論有重要的指導作用。作為GLaDOS的算法模塊，你要完成這個任務。本題時限為2000ms

Input

第一行一個整數n。之后n-1行，每行三個整數ui，vi，ai ,表示有一條從ui 連向vi ，花費時間為ai 的通道。

Output

一行一個數T，表示最小的脫逃時間。

Sample Input

5 1 2 2 2 3 3 2 4 5 1 5 1

Sample Output

13樣例說明 1--> open1--> 5--> open2--> use(1)--> 2--> 3--> open2--> use(1)--> 2--> 4--> open2--> use(1)--> exit

Data Constraint

Solution　

?

　　我們可以采用動態規劃來求解?dp[i][0/1]

　　0表示在i點及i點兒子設傳送門所能得到的最大總和

　　1 表示不在i點及i點兒子設傳送門所能得到的最大總和

　　首先，對于dp[i][1]的情況，一定存在i點的祖先中有傳送門，這樣才能使結果更優。所以對于他的每一個兒子都能跳回到他的祖先。但實際上只有使一個兒子跳回祖先時，才能保證fa->i的邊經過兩次。

　　否則轉化為dp[i][0]的情況。則我們要使選的兒子最優。

　　dp[i][1]=max(dp[vi][1]+wi);

　　其次，對于dp[i][0]的情況，在每個兒子中設立傳送門并不會影響到其他兒子，因為總能從兒子回到i時再在i重設傳送門。所以我們就取每個兒子設與不設的最優值之和。

　　dp[i][0]=max(dp[vi][0],dp[vi][1]+wi);

?

1 #include <cstdio> 2 #define N 1000007 3 #define LL long long 4 using namespace std; 5 struct arr { 6 long long w; 7 int x,y,next; 8 }; 9 arr edge[N*2]; 10 int ls[N],n; 11 LL f[N][2],ans; 12 bool p[N]; 13 14 LL max(LL x,LL y){ 15 if (x>y) return x; 16 return y; 17 } 18 19 int dfs(int s){ 20 int i=ls[s]; 21 while (i!=0){ 22 int d=edge[i].y; 23 if (p[d]){ 24 p[d]=false; 25 dfs(d); 26 f[s][1]=max(f[s][1],f[d][1]+edge[i].w); 27 f[s][0]+=max(f[d][0],f[d][1]+edge[i].w); 28 } 29 i=edge[i].next; 30 } 31 } 32 33 int add(int x,int y,LL w,int e){ 34 edge[e].x=x; edge[e].y=y; edge[e].w=w; 35 edge[e].next=ls[edge[e].x]; ls[edge[e].x]=e; 36 edge[--e].x=y; edge[e].y=x; edge[e].w=w; 37 edge[e].next=ls[edge[e].x]; ls[edge[e].x]=e; 38 } 39 40 int main() 41 { 42 scanf("%d",&n); 43 ls[1]=1; 44 for (int i=1;i<n;i++){ 45 int x,y; 46 LL w; 47 scanf("%d%d%lld",&x,&y,&w); 48 add(x,y,w,i*2); 49 ans+=w*2; 50 } 51 for (int i=1;i<=n;i++) 52 p[i]=true; 53 p[1]=false; 54 dfs(1); 55 ans-=max(f[1][1],f[1][0]); 56 printf("%lld\n",ans); 57 } View Code

?

?

?

轉載于:https://www.cnblogs.com/Tokisaki-Kurumi/p/9800966.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JZOJ5906 传送门的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。