hdu4003Find Metal Mineral 树形dp+分组背包

分类：dp

树形dp分组背包

;const int maxn = 10010 ;const int inf = 0x3f3f3f3f;int dp[maxn][60] ;int head[maxn] ;int nedge ;int n , s , m;struct Edge{int v , w ;int next ;}edge[maxn<<1] ;void addedge(int u , int v , int w){edge[nedge].v = v ;edge[nedge].w = w;edge[nedge].next = head[u] ;head[u] = nedge++;}void dfs(int u , int pre){int flag = 0 ;for(int i = head[u] ;i != -1 ;i =edge[i].next){int v = edge[i].v ;if(v == pre)continue ;dfs(v , u) ;int len = edge[i].w ;for(int j = m;j >= 0;j–){int sum = inf ;for(int k = 0;k <= j;k++){int tmp = (k == 0 ? 2*len : k*len);sum = min(sum , dp[u][j-k] + dp[v][k] + tmp) ;}dp[u][j] = sum;}}}int main(){ //freopen(“in.txt” ,”r” , stdin) ;while(~scanf(“%d%d%d” ,&n , &s , &m)){memset(head , -1 , sizeof(head)) ;memset(dp , 0 ,sizeof(dp)) ;nedge = 0 ;for(int i = 1;i < n;i++){int u , v , w ;scanf(“%d%d%d” , &u , &v , &w) ;addedge(u , v , w) ;addedge(v , u , w) ;}dfs(s,0) ;cout<<dp[s][m]<<endl;}return 0 ;}

上一篇hdu3499Consumer 依赖背包模板

顶0踩0

，唯有讲述此间途经的美景，分享没有男主角的相片。

相关文章：

你感兴趣的文章：

标签云：