Problem Description In the battlefield , an effective way to defeat enemies is to break their communication system.
5 5 1 3 2 1 4 3 3 5 5 4 2 6 0 0
3
/** hdu 3586 樹形dp二分求解 題目大意:給定一棵樹n個點,點1是根節點,每個葉子節點都向根節點傳遞“消息”,我們要在一些路上阻止,使路徑不通。每條路上的阻止代價為該路權值, 我們能阻止的權值有一個上限x,而且所有葉子節點阻止的代價和不能超過m。問最小的可行x 解題思路:假設我們已經到了一個x,那麼以u為根節點的子樹的總花費dp[u],若邊權值w<=x,dp[u]+=min(dp[v],w),否則dp[u]+=min(dp[v],inf), 這裡的inf為任意一個大於m的數(但注意不要爆掉int,我取的m+1)。解釋一下為什麼用inf,因為w值已經超過限制我們不能阻止w邊了, 那麼要阻止以v為根節點子樹的所有葉子節點,只能是dp[v]了。這樣樹形dp就可以求出dp[1],和m比較即可知道我們的x值合不合適了。 對於x二分就可以了。 */ #include#include #include #include using namespace std; const int maxn=1005; struct note { int v,w,next; }edge[maxn*2]; int head[maxn],ip; int n,m,mid,dp[maxn]; void init() { memset(head,-1,sizeof(head)); ip=0; } void addedge(int u,int v,int w) { edge[ip].v=v,edge[ip].w=w,edge[ip].next=head[u],head[u]=ip++; } void dfs(int u,int pre) { int flag=0; for(int i=head[u];i!=-1;i=edge[i].next)///求解父親節點前它的所有兒子節點必須全部已經求出 { int v=edge[i].v; if(v==pre)continue; flag=1; dfs(v,u); } if(flag==0)///葉子節點 { dp[u]=m+1;///任意一個大於m的數 return; } int t=0; for(int i=head[u];i!=-1;i=edge[i].next) { int w=edge[i].w; int v=edge[i].v; if(v==pre)continue; if(w<=mid) dp[u]+=min(dp[v],w); else dp[u]+=min(dp[v],m+1); } } int main() { while(~scanf(%d%d,&n,&m)) { if(n==0&&m==0)break; int maxx=0; init(); for(int i=0;i >1; memset(dp,0,sizeof(dp)); dfs(1,-1); // printf(%d %d ,mid,dp[1]); if(dp[1]<=m) { flag=1; r=mid; } else l=mid+1; } if(flag==0) printf(-1 ); else printf(%d ,r); } return 0; } /** 5 4 1 3 2 1 4 3 3 5 5 4 2 6 5 4 1 3 2 1 4 2 3 5 5 4 2 6 5 3 1 3 2 1 4 2 3 5 5 4 2 6 */