Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 1668 Accepted Submission(s): 618
HDU 3586:
题目意思;
打断一棵树的叶子节点和根节点之间的联系，要求只有士兵的能力大于这条边所需要的能力时才能被打断，同时满足所有消耗的能力值之和不大于m，求士兵所具有的最小的能力值；
解题思路：
首先对士兵的能力值在一个区间内进行二分，然后对于每一个值进行dp，状态转移方程为：
if(dp[son]>cost[father][son]&&cost[father][cost]<=mid)
dp[son]=cost[father][son];
然后求到根节点的时候，把根节点的儿子节点的所有dp值都加起来如果小于等于m，则返回真值，否则，返回0；
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<vector> 7 using namespace std; 8 const int maxn=2010; 9 const int inf=1000001; 10 vector<int> G[maxn]; 11 int cost[maxn][maxn]; 12 int n,m,head,mid; 13 int dfs(int parent,int point) 14 { 15 int ans=0; 16 for(int i=0;i<G[point].size();i++) 17 { 18 if(G[point][i]==parent) continue; 19 int result=dfs(point,G[point][i]); 20 if(cost[point][G[point][i]]<=result&&cost[point][G[point][i]]<=mid) 21 { 22 result=cost[point][G[point][i]]; 23 } 24 ans+=result; 25 } 26 if(!ans) return inf; 27 return ans; 28 } 29 int main() 30 { 31 // freopen("in.txt","r",stdin); 32 int u,v,c; 33 while(~scanf("%d%d",&n,&m)){ 34 if(!n&&!m) break; 35 int l=inf,r=0; 36 for(int i=0;i<maxn;i++) while(!G[i].empty()) G[i].pop_back(); 37 for(int i=0;i<n-1;i++) 38 { 39 scanf("%d%d%d",&u,&v,&c); 40 if(c<l) l=c; 41 if(c>r) r=c; 42 G[u].push_back(v); 43 G[v].push_back(u); 44 cost[u][v]=cost[v][u]=c; 45 } 46 int ans=-1; 47 while(l<=r){ 48 mid=(l+r)>>1; 49 if(dfs(0,1)<=m){ 50 ans=mid; 51 r=mid-1; 52 } 53 else l=mid+1; 54 } 55 printf("%d\n",ans); 56 } 57 return 0; 58 }
原文：http://www.cnblogs.com/codeyuan/p/4312158.html