题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3586
http://blog.csdn.net/woshi250hua/article/details/7639423
题目大意：给定n个敌方据点，1为司令部，其他点各有一条边相连构成一棵树，每条边都有一个权值cost表示破坏这条边的费用，叶子节点为前线。现要切断前线和司令部的联系，每次切断边的费用不能超过上限limit，问切断所有前线与司令部联系所花费的总费用少于m时的最小limit。1<=n<=1000,1<=m<=100万
先考虑x的代价能否满足条件。对于某个节点rt有两种情况。
if(tree[i].val < x) dp[rt] += min(tree[i].val,dp[son])
else dp[rt]+=dp[son];
因为这里只用给叶子节点赋值，因为是双向边，不能用head[rt]==-1判断。这里可以用flag来判断。
x的情况分析好后，就可以用二分来找到答案了
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 1000+5 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f int n,m; struct node{int y,val,next;}tree[MAXN<<2]; int head[MAXN],vis[MAXN],ptr=1,dp[MAXN]; void init() { mem(head,-1); mem(vis,0); mem(dp,0); ptr=1; } void add(int x,int y,int val) { tree[ptr].y = y; tree[ptr].val = val; tree[ptr].next = head[x]; head[x] = ptr++; } int cost; void dfs(int rt,int limit) { vis[rt]=1; int flag = 0; for(int i = head[rt];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; flag = 1; dfs(y); if(tree[i].val < limit) { dp[rt] += min(tree[i].val,dp[y]); } else { dp[rt] += dp[y]; } } if(!flag) dp[rt]=INF; } int main() { int i,j,k,t; while(~sf("%d%d",&n,&m)) { init(); int mx = 0; for(i=1;i<n;i++) { int x,y,z; sf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); if(z>mx) mx = z; } dfs(1); int lo = 1,hi = mx,mid; while(lo<=hi) { mem(dp,0); mem(vis,0); mid = (lo+hi)>>1; dfs(1,mid); if(dp[1]<=m) hi = mid-1; else lo = mid+1; } pf("%d ",lo); } }