题目链接：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中判断是不是都能切断叶子节点的联系。
#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
int to[N << ], Next[N << ], cost[N << ], head[N], tot, dp[N], inf = 1e6 + ; void init() {
memset(head, -, sizeof(head));
tot = ;
}
inline void add_edge(int u, int v, int c) {
Next[tot] = head[u];
to[tot] = v;
cost[tot] = c;
head[u] = tot++;
}
void dfs(int u, int p, int limit) {
dp[u] = inf;
bool inter = false;
for(int i = head[u]; ~i; i = Next[i]) {
int v = to[i];
if(v == p)
continue;
dfs(v, u, limit);
if(!inter) {
dp[u] = ;
inter = true;
}
if(cost[i] <= limit) {
dp[u] += min(dp[v], cost[i]);
} else {
dp[u] += dp[v];
}
}
}
void solve() {
int n, m, u, v, c;
while(~scanf("%d %d", &n, &m) && (n || m)) {
init();
for(int i = ; i < n; ++i) {
scanf("%d %d %d", &u, &v, &c);
add_edge(u, v, c);
add_edge(v, u, c);
}
int l = , r = ;
while(l < r) {
int mid = (l + r) >> ;
dfs(, -, mid);
if(dp[] <= m) {
r = mid;
} else {
l = mid + ;
}
}
if(r == ) {
printf("-1\n");
} else {
printf("%d\n", l);
}
}
} int main()
{
solve();
return ;
}