[HDU3586]Information Disturbing（DP + 二分）

传送门

题意：给定一个带权无向树，要切断所有叶子节点和1号节点（总根）的联系，每次切断边的费用不能超过上限limit，问在保证总费用<=m下的最小的limit

二分答案，再 DP，看看最终结果是否小于 m

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 1001 5 #define max(x, y) ((x) > (y) ? (x) : (y)) 6 7 int n, m, cnt, ans; 8 int a[N], sum[N], head[N], to[N << 1], val[N << 1], next[N << 1]; 9 bool vis[N]; 10 11 inline int read() 12 19 20 inline void add(int x, int y, int z) 21 27 28 inline void dfs(int u, int x) 29 43 else sum[u] += sum[v]; 44 } 45 } 46 } 47 48 inline bool check(int x) 49 58 59 int main() 60 78 x = 1, y = m, ans = 1; 79 while(x <= y) 80 85 printf("%d\n", ans); 86 } 87 return 0; 88 }
View Code

上一篇：[luoguP3047] [USACO12FEB]附近的牛Nearby Cows（DP）

下一篇：[luoguP1474] 货币系统 Money Systems（背包）

---

二分 DP