本文共 1752 字，大约阅读时间需要 5 分钟。
1、
参考
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 #include #include using namespace std;#define N 1005#define INF 1000005int 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]; else dp[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 >1;//printf("mid=%d\n",mid); dfs(1,0); if(dp[1]<=m) { r=mid-1; ans=min(mid,ans); } else l=mid+1; } if(ans==INF) printf("-1\n"); else printf("%d\n",ans); } return 0;}
转载地址：http://rrddi.baihongyu.com/