简单的树形dp，dp[i][0]表示不选i节点以i为根的子树获得的最大值。既然根节点不选，那么子节点只能选一个，否则无法保证连通。根节点若选的话则把所有状态值为正的节点都选了既为最优值

1 #include
      
        2 #include
       
         3 #define N 1005 4 int max(int a,int b) 5 { 6     return a>b?a:b; 7 } 8 int dir[4][2]={
    0,1,0,-1,1,0,-1,0}; 9 int head[N],t;10 struct edge11 {12     int v,next;13 };14 edge e[2*N];15 int val[N];16 struct point17 {18     int x,y;19 };20 point p[N];21 void add(int u,int v)22 {23     e[t].v=v;24     e[t].next=head[u];25     head[u]=t++;26 }27 int dp[N][2];28 bool used[N];29 void init()30 {31     memset(used,0,sizeof(used));32     memset(head,-1,sizeof(head));33     t=0;34 }35 void dfs(int u)36 {37     used[u]=true;38     int i,v;39     dp[u][0]=0;40     dp[u][1]=val[u];41     for(i=head[u];i>=0;i=e[i].next)42     {43         v=e[i].v;44         if(!used[v])45         {46             dfs(v);47             dp[u][0]=max(dp[u][0],max(dp[v][0],dp[v][1]));48             if(dp[v][1]>0)49             dp[u][1]+=dp[v][1];50         }51     }52 }53 int main()54 {55     int n;56     int i,j,k;57     scanf("%d",&n);58     init();59     for(i=1;i<=n;i++)60     {61         scanf("%d%d%d",&p[i].x,&p[i].y,&val[i]);62         for(j=1;j