HDU 3586 Information Disturbing(二分+数形DP) - c++编程基础

题目：给出n个士兵，其中1号为指挥官，关系为树状结构，叶子为先锋，现在要在总花费小于m的情况切断所有的先锋与指挥官的联系，问最大的限制最小为多少
http://acm.hdu.edu.cn/showproblem.php pid=3586
题目要问的是最小的最大限制，必然二分答案
然后对于每一个值，树形DP判定是否可行
dp[i]表示要切断以i为根的其它所有子树的最小代价。
其中设定叶子结点的代价为无穷大
那么对于某一个非叶子结点，要切断一棵子树就有两种选择，切断以孩子为根的子树或者切断根与孩子的边。
如果根与孩子的边大于限制，那就取无穷大。
最后判断1号结点的总花费是否小于等于m
注意：无穷大不要取太大，否则会连续相加溢出
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a) #define inf 1<<20
#define N 100005
#define pi acos(-1.0)
#define pb(a) push_back(a)
#define lson step<<1
#define rson step<<1|1
using namespace std;
struct Node{
int v,w,next;
}edge[100005];
int start[1005],tot;
int n,m,dp[1005];
void addedge(int u,int v,int w){

edge[tot].v=v;edge[tot].w=w;
edge[tot].next=start[u];
start[u]=tot++;
}
void _addedge(int u,int v,int w){
addedge(u,v,w);
addedge(v,u,w);
}
void dfs(int u,int limit,int pre){
bool flag=false;
for(int i=start[u];i!=-1;i=edge[i].next){
int v=edge[i].v,w=edge[i].w;
if(v==pre) continue;
flag=true;
dfs(v,limit,u);
dp[u]+=min(dp[v],w>limit inf:w);
}
if(!flag) dp[u]=inf;
}
bool check(int limit){
memset(dp,0,sizeof(dp));
dfs(1,limit,-1);
// cout< if(dp[1]>m) return false;
return true;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF&&n+m){
tot=0;memset(start,-1,sizeof(start));
for(int i=1;i int u,v,w;
scanf("%d%d%d",&u,&v,&w);
_addedge(u,v,w);
}
int low=0,high=m,mid,ok=0,ans=-1;
while(low<=high){
mid=(low+high)/2;
if(check(mid)) {ans=mid;high=mid-1;}
else low=mid+1;
}
printf("%d\n",ans);
}
return 0;
}