HDU 3586 Information Disturbing 树形DP

发布时间:2016-12-9 17:53:03 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 3586 Information Disturbing 树形DP",主要涉及到HDU 3586 Information Disturbing 树形DP方面的内容,对于HDU 3586 Information Disturbing 树形DP感兴趣的同学可以参考一下。

  代码1: #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define maxn 1003 #define inf 1<<29 struct node { int v, next, w; }edge[maxn<<1]; int n, m; int head[maxn]; int tot; void init() { tot = 0; memset(head, -1, sizeof(head)); } void add(int x, int y, int w) { edge[tot].v = y; edge[tot].w = w; edge[tot].next = head[x]; head[x] = tot++; } int minz(int a, int b) { return a < b ? a : b; } int dp[1003]; void dfs(int u, int pre, int sum) { int i; bool flag = 0; int tmp = 0; for(i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; int w = edge[i].w; if(v == pre) continue; dfs(v, u, sum); flag = 1; if(w <= sum) tmp += minz(dp[v], w); else { if(dp[v] < inf) tmp += dp[v]; else flag = 0; } if(!flag) break; } if(flag) dp[u] = minz(dp[u], tmp); } int main() { int i, j; int x, y, w; while( ~scanf("%d%d", &n, &m) && (n||m) ) { init(); for(i = 0; i < n-1; i++) { scanf("%d%d%d", &x, &y, &w); add(x, y, w); add(y, x, w); } int l = 0, r = m; while(l <= r) { int mid = (l + r) >> 1; for(i = 1; i <= n; i++) dp[i] = inf; dfs(1, 1, mid); if(dp[1] > m) l = mid + 1; else r = mid - 1; //printf("l = %d r = %d\n", l, r); } if(l > m) puts("-1"); else printf("%d\n", l); } return 0; } 代码2: #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define maxn 1003 #define inf 1000001 //注意别太大,不然会超int struct node { int v, next, w; }edge[maxn<<1]; int head[maxn]; int tot; int n, m; void init() { tot = 0; memset(head, -1, sizeof(head)); } void add(int x, int y, int w) { edge[tot].v = y; edge[tot].w = w; edge[tot].next = head[x]; head[x] = tot++; } int minz(int a, int b) { return a < b ? a : b; } int dp[1003]; void dfs(int u, int pre, int sum) { int i; bool flag = 0; int tmp = 0; for(i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; int w = edge[i].w; if(v == pre) continue; //printf("v = %d w = %d\n", v, w); dfs(v, u, sum); if(w <= sum) tmp += minz(dp[v], w); else tmp += dp[v]; flag = 1; } if(flag) dp[u] = minz(dp[u], tmp); } int main() { int i, j; int x, y, w; while( ~scanf("%d%d", &n, &m) && (n||m) ) { init(); for(i = 0; i < n-1; i++) { scanf("%d%d%d", &x, &y, &w); add(x, y, w); add(y, x, w); } int l = 0, r = m; while(l <= r) { int mid = (l + r) >> 1; for(i = 1; i <= n; i++) dp[i] = inf; dfs(1, 1, mid); if(dp[1] > m) l = mid + 1; else r = mid - 1; //printf("l = %d r = %d\n", l, r); } if(l > m) puts("-1"); else printf("%d\n", l); } return 0; }

上一篇:C++时间函数
下一篇:POJ 1655 Balancing Act 树形DP入门题

相关文章

相关评论