当前位置: 代码迷 >> 综合 >> poj 1849 Two 树形dp好题
  详细解决方案

poj 1849 Two 树形dp好题

热度:50   发布时间:2024-01-19 05:29:47.0

题意:

可以转换为于在一棵树中,找m个叶子节点,使他们连线(重复部分只计一次)的距离和最大。

分析:

m==2时求树的直径倒是简单,m>2时就要用树形dp了,有n*m^2的树形dp.对于树形dp,不仅仅每一棵子树可以看做一个子问题,每一个作为子树的子问题也可以看成是由一些更小的子问题构成,代码中的这种思想用滚动数组实现了。

代码:

//poj 1849
//sep9
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=100024;
vector<int> g[MAXN],val[MAXN];
int dp[MAXN][3];void dfs(int u,int p)
{for(int i=g[u].size()-1;i>=0;--i){int v=g[u][i];if(p==v) continue;dfs(v,u);for(int j=2;j>=0;--j){dp[u][j]=dp[u][j]+dp[v][0]+2*val[u][i];for(int s=1;s<=j;++s)dp[u][j]=min(dp[u][j],dp[u][j-s]+dp[v][s]+s*val[u][i]);			}}	
}int main()
{int n,s;scanf("%d%d",&n,&s);for(int i=1;i<=n;++i) g[i].clear();for(int i=1;i<n;++i){int u,v,w;scanf("%d%d%d",&u,&v,&w);g[u].push_back(v),g[v].push_back(u);val[u].push_back(w),val[v].push_back(w);	}memset(dp,0,sizeof(dp));dfs(s,-1);printf("%d",dp[s][2]);return 0;	
} 


  相关解决方案