Information Disturbing
题目：http://acm.hdu.edu.cn/showproblem.php?pid=3586
题意：给定n个敌方据点，1为司令部，其他点各有一条边相连构成一棵树，每条边都有一个权值cost表示破坏这条边的费用，叶子节点为前线。现要切断前线和司令部的联系，每次切断边的费用不能超过上限limit，问切断所有前线与司令部联系所花费的总费用少于m时的最小limit。
题解：一般看出这题要树形DP不难，但是难在想到要二分。对于上限进行二分，然后通过树形DP进行判断。
代码：
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 1010
#define inf (0xfffff)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int edge[MAX<<1];//表示第i条边的终点
int next[MAX<<1];//与第i条边同起点的下一条边的位置
int head[MAX<<1];//以i为起点的第一条边的储存位置
int cost[MAX<<1];
int dp[MAX];
void insert(int i,int a,int b,int c)//a起点,b终点
{
edge[i]=b;
next[i]=head[a];
head[a]=i;
cost[i]=c;
}
void dfs(int x,int pre,int maxx)
{
bool flag=false;
int total=0;
for(int i=head[x]; i!=-1; i=next[i])
{
int k=edge[i];
if(k!=pre)
{
flag=true;
dfs(k,x,maxx);
if(cost[i]>maxx) total+=dp[k];
else total+=min(dp[k],cost[i]);
}
}
if(flag) dp[x]=total;
else dp[x]=inf;
}
int main()
{
int n,m;
int a,b,c;
for(; scanf("%d%d",&n,&m);)
{
if(n+m==0) break;
int len=0,ans=inf;
memset(head,-1,sizeof(head));
memset(next,-1,sizeof(next));
for(int i=1,j=1; i<n; ++i)
{
scanf("%d%d%d",&a,&b,&c);
insert(j++,a,b,c);
insert(j++,b,a,c);
len=max(c,len);
}
int l=1,r=len,mid;
for(; l<=r;)
{
memset(dp,0,sizeof(dp));
mid=(l+r)>>1;
dfs(1,-1,mid);
if(dp[1]<=m)
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
if(ans==inf) puts("-1");
else printf("%d\n",ans);
}
return 0;
}