本文主要是介绍hdu 3586 Information Disturbing(树形DP+二分查找+删变暖)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、http://acm.hdu.edu.cn/showproblem.php?pid=3586
参考http://blog.csdn.net/roney_win/article/details/11353409
http://blog.csdn.net/woshi250hua/article/details/7639423
2、题目大意：
N个人组成一棵树，编号1-N，其中编号为1的人为总司令，叶节点为前线士兵。点与点之间的边有一定的权值，代表砍掉这条边所要花费的代价。题目要求砍掉某些边使得所有的叶节点都无法与根节点联通，而且在满足砍掉的所有的边的和<=m的情况下的最小限制，这里的限制是指砍掉的边中的权值最大的数。
这是一个判定性问题，就是问某个limit是否能够满足条件切断所有前线与司令部的联系，然后找符合条件的最大limit就可以了。想通这点以后就可以二分答案，下限为1，上限为最大的边权，再写一个dfs(limit)，判断切断所有前线联系时花费的最小费用是否小等于m，是的话就往后查找，否则向前。
设dp[i]为切断i的所有子孙叶子所花费的最小费用，
状态转移方程
if(w[i]>mid) dp[u]+=dp[vv];//如果w[i]>mid，即大于上限，不能删除该边，只能来源于字节点的更新值
else dp[u]+=min(dp[vv],w[i]);
3、AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1005
#define INF 1000005
int head[N*2],next[N*2],v[N*2],w[N*2];
int dp[N];//dp[i]表示以i点为根使得叶子节点都不连通的最小代价
int tot,mid;
void add_edge(int a,int b,int c)
{v[tot]=b;w[tot]=c;next[tot]=head[a];head[a]=tot++;
}
void dfs(int u,int fa)
{if(head[u]==-1)//判断是不是跟结点{printf("u=%d\n",u);dp[u]=INF;return;}else if((next[head[u]]==-1 ) && v[head[u]]==fa){dp[u]=INF;return ;}dp[u]=0;for(int i=head[u];i!=-1;i=next[i]){int vv=v[i];if(vv!=fa){dfs(vv,u);if(w[i]>mid)dp[u]+=dp[vv];elsedp[u]+=min(dp[vv],w[i]);}}
}
int main()
{int n,m,a,b,c,l,r;while(scanf("%d%d",&n,&m)!=EOF){if(n==0 && m==0)break;tot=0;memset(head,-1,sizeof(head));memset(dp,0,sizeof(dp));l=INF;r=-INF;for(int i=1;i<n;i++){scanf("%d%d%d",&a,&b,&c);add_edge(a,b,c);add_edge(b,a,c);l=min(l,c);r=max(r,c);}int ans=INF;//printf("l=%d r=%d\n",l,r);while(l<=r){mid=(l+r)>>1;//printf("mid=%d\n",mid);dfs(1,0);if(dp[1]<=m){r=mid-1;ans=min(mid,ans);}elsel=mid+1;}if(ans==INF)printf("-1\n");elseprintf("%d\n",ans);}return 0;
}
这篇关于hdu 3586 Information Disturbing(树形DP+二分查找+删变暖)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
