HDU 3586 Information Disturbing(二分+数形DP)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
不知道做什么了，找个水题做做
题目：给出n个士兵，其中1号为指挥官，关系为树状结构，叶子为先锋，现在要在总花费小于m的情况切断所有的先锋与指挥官的联系，问最大的限制最小为多少
http://acm.hdu.edu.cn/showproblem.php?pid=3586
题目要问的是最小的最大限制，必然二分答案
然后对于每一个值，树形DP判定是否可行
dp[i]表示要切断以i为根的其它所有子树的最小代价。
其中设定叶子结点的代价为无穷大
那么对于某一个非叶子结点，要切断一棵子树就有两种选择，切断以孩子为根的子树或者切断根与孩子的边。
如果根与孩子的边大于限制，那就取无穷大。
最后判断1号结点的总花费是否小于等于m
注意：无穷大不要取太大，否则会连续相加溢出
#include<iostream>#include<fstream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<set>#include<map>#include<queue>#include<stack>#include<string>#include<vector>#include<ctime>#include<sstream>#include<cassert>#define LL long long#define eps 1e-7#define zero(a) fabs(a)<eps#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|1using 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<<limit<<" "<<dp[1]<<" "<<dp[2]<<" "<<dp[3]<<" "<<dp[4]<<endl; 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<n;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;}