題意：題目敘述很長，但很簡單，其實如果是英文題倒還可以狠狠的惡心一下人的= =！就是給一個無向樹，求最大權子樹

題解：樹形dp，dp[i][0]代表不要第i個點時以i為根的子樹的最大價值，dp[i][1]代表必須要i時以i為根的子樹的最大值。于是dp[i][0]=max(dp[i][0],dp[j][0],dp[j][1])，j為i能到的點，dp[i][1]=val+sum(max(dp[j][1],0))，即取所有權值為正的i的子樹與它相連，注意必須是dp[i][1]，因為要保證樹最后的連通性。

View Code 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1005; 6 int head[N],nc; 7 struct Edge 8 { 9 int to,next; 10 }edge[N*5]; 11 int val[N],dp[N][2]; 12 bool vis[N]; 13 void add(int a,int b) 14 { 15 edge[nc].to=b;edge[nc].next=head[a];head[a]=nc++; 16 edge[nc].to=a;edge[nc].next=head[b];head[b]=nc++; 17 } 18 void dfs(int now) 19 { 20 dp[now][1]=val[now]; 21 dp[now][0]=0; 22 vis[now]=true; 23 for(int i=head[now];i!=-1;i=edge[i].next) 24 { 25 int to=edge[i].to; 26 if(!vis[to]) 27 { 28 dfs(to); 29 dp[now][1]+=max(dp[to][1],0); 30 dp[now][0]=max(dp[now][0],max(dp[to][1],dp[to][0])); 31 } 32 } 33 } 34 int po[N][2]; 35 int main() 36 { 37 int n; 38 while(scanf("%d",&n)!=EOF) 39 { 40 memset(head,-1,sizeof(head)); 41 memset(vis,false,sizeof(vis)); 42 nc=0; 43 for(int i=0;i<n;i++) 44 { 45 scanf("%d%d%d",&po[i][0],&po[i][1],&val[i]); 46 for(int j=0;j<i;j++) 47 { 48 if(abs(po[i][0]-po[j][0])+abs(po[i][1]-po[j][1])==1) 49 add(i,j); 50 } 51 } 52 dfs(0); 53 printf("%d\n",max(dp[0][0],dp[0][1])); 54 } 55 return 0; 56 }

轉載于:https://www.cnblogs.com/tmeteorj/archive/2012/09/18/2691431.html

總結

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

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