题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3586
给定n个敌方据点，1为司令部，其他点各有一条边相连构成一棵树，每条边都有一个权值cost表示破坏这条边的费用，叶子节点为前线。现要切断前线和司令部的联系，每次切断边的费用不能超过上限limit，问切断所有前线与司令部联系所花费的总费用少于m时的最小limit。1<=n<=1000,1<=m<=10^6
dp[i]表示i节点为root的这个子树所破坏的最少费用，if(cost[i][i->son] <= limit) dp[i] += min(dp[i->son], cost[i][i->son]);
二分limit，然后把limit放到dfs中判断是不是都能切断叶子节点的联系。
1 #pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime> 10 #include <list> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL; 15 typedef pair <int, int> P; 16 const int N = 1e5 + 5; 17 int to[N << 1], Next[N << 1], cost[N << 1], head[N], tot, dp[N], inf = 1e6 + 7; 18 19 void init() { 20 memset(head, -1, sizeof(head)); 21 tot = 0; 22 } 23 inline void add_edge(int u, int v, int c) { 24 Next[tot] = head[u]; 25 to[tot] = v; 26 cost[tot] = c; 27 head[u] = tot++; 28 } 29 void dfs(int u, int p, int limit) { 30 dp[u] = inf; 31 bool inter = false; 32 for(int i = head[u]; ~i; i = Next[i]) { 33 int v = to[i]; 34 if(v == p) 35 continue; 36 dfs(v, u, limit); 37 if(!inter) { 38 dp[u] = 0; 39 inter = true; 40 } 41 if(cost[i] <= limit) { 42 dp[u] += min(dp[v], cost[i]); 43 } else { 44 dp[u] += dp[v]; 45 } 46 } 47 } 48 void solve() { 49 int n, m, u, v, c; 50 while(~scanf("%d %d", &n, &m) && (n || m)) { 51 init(); 52 for(int i = 1; i < n; ++i) { 53 scanf("%d %d %d", &u, &v, &c); 54 add_edge(u, v, c); 55 add_edge(v, u, c); 56 } 57 int l = 1, r = 1001; 58 while(l < r) { 59 int mid = (l + r) >> 1; 60 dfs(1, -1, mid); 61 if(dp[1] <= m) { 62 r = mid; 63 } else { 64 l = mid + 1; 65 } 66 } 67 if(r == 1001) { 68 printf("-1 "); 69 } else { 70 printf("%d ", l); 71 } 72 } 73 } 74 75 int main() 76 { 77 solve(); 78 return 0; 79 }