5 5 1 3 2 1 4 3 3 5 5 4 2 6 0 0
3
题意：切断一定的边，使得所有叶子节点与根节点断开，限制条件是断开的边权之和小于某一值，且每一条边权小于某一值x，求x的最小值。
一看题就知道是二分+树形dp判断可行性， INF上界不能太大，否则会溢出，因为这个wa好多次。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-6 16:15:10
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 1000000
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=4009;
int head[maxn],tol;
struct node{
int next,to,val;
node(){};
node(int _next,int _to,int _val):next(_next),to(_to),val(_val){}
}edge[5*maxn];
void add(int u,int v,int val){
edge[tol]=node(head[u],v,val);
head[u]=tol++;
}
int dfs(int u,int fa,int num){
int sum=0,flag=0;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v==fa)continue;
int tt=dfs(v,u,num);
if(tt>edge[i].val&&edge[i].val<=num)
tt=edge[i].val;
sum+=tt;
flag=1;
}
if(!flag)return INF;
return sum;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int i,j,k,m,n;
while(~scanf("%d%d",&n,&m)){
if(n==0||m==0)break;
memset(head,-1,sizeof(head));tol=0;
int l=1,r=1010;
for(i=1;i<n;i++){
int p;
scanf("%d%d%d",&j,&k,&p);
add(j,k,p);
add(k,j,p);
}
int ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(dfs(1,1,mid)<=m)
ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<endl;
//cout<<dfs(1,-1,3)<<" "<<dfs(1,-1,4)<<endl;
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/18951369