题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3586
题目大意：给定n个敌方据点，编号1为司令部，其他点各有一条边相连构成一棵树，每条边都有一个权值cost表示破坏这条边的费用，叶子节点为前线。现要切断前线和司令部的联系，每次切断边的费用不能超过上限limit，问切断所有前线与司令部联系所花费的总费用少于m时的最小limit。1<=n<=1000,1<=m<=100万。
思路：很容易想到DP，定义dp[root]表示以root为根节点的子树失去与其叶子节点的链接的最小花费，那么如果其与孩子的边权小于limit，则dp[root]+=min(dp[son],w)(son为root的孩子，w为相连的边的权值)，否则的话,dp[root]+=dp[son];
那么怎样确定limit值呢，由于问题是求使总花费不超过m的最小的limit值，当然就是二分答案了，确定limit的值的下限为1，上限为最大的边值，然后对于limit进行二分查找，如果最后求的总的花费值小于等于m,则往前找，否则就往后找。
代码如下：
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define MAX 1010
#define INF 1000010
class node
{
public:
int to;
int w;
int next;
};
node edge[*MAX];
int head[MAX];
int n,m;
int tol;
int dp[MAX];
int vis[MAX];
void init()
{
tol=;
memset(head,-,sizeof(head));
}
void Build_Tree(int u,int v,int w)
{
edge[tol].to=v;
edge[tol].w=w;
edge[tol].next=head[u];
head[u]=tol++;
}
int low,high,mid;
void dfs(int root,int pre)
{
vis[root]=;
int flag=;
for(int i=head[root];i!=-;i=edge[i].next)
{
if(vis[edge[i].to]) continue;
flag=;
int cost=edge[i].w;
int son=edge[i].to;
dfs(son,root);
if(cost<=mid) dp[root]+=min(dp[son],cost);
else dp[root]+=dp[son];
}
if(flag==) dp[root]=INF;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
if(n==&&m==) break;
low=;high=; for(int i=;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(high<w) high=w;
Build_Tree(u,v,w);
Build_Tree(v,u,w);
}
int ans=-;
while(low<=high)
{
memset(dp,,sizeof(dp));
memset(vis,,sizeof(vis));
mid=(low+high)/;
dfs(,-);
if(dp[]>m) low=mid+;
else {high=mid-;ans=mid;}
}
cout<<ans<<endl;
}
return ;
}