hdu3586 樹形dp+二分求解

hdu3586 樹形dp+二分求解

 

 

Problem Description In the battlefield , an effective way to defeat enemies is to break their communication system.
The information department told you that there are n enemy soldiers and their network which have n-1 communication routes can cover all of their soldiers. Information can exchange between any two soldiers by the communication routes. The number 1 soldier is the total commander and other soldiers who have only one neighbour is the frontline soldier.
Your boss zzn ordered you to cut off some routes to make any frontline soldiers in the network cannot reflect the information they collect from the battlefield to the total commander( number 1 soldier).
There is a kind of device who can choose some routes to cut off . But the cost (w) of any route you choose to cut off can’t be more than the device’s upper limit power. And the sum of the cost can’t be more than the device’s life m.
Now please minimize the upper limit power of your device to finish your task.

Input The input consists of several test cases.
The first line of each test case contains 2 integers: n(n<=1000）m(m<=1000000).
Each of the following N-1 lines is of the form:
ai bi wi
It means there’s one route from ai to bi(undirected) and it takes wi cost to cut off the route with the device.
(1<=ai,bi<=n,1<=wi<=1000)
The input ends with n=m=0.

Output Each case should output one integer, the minimal possible upper limit power of your device to finish your task.
If there is no way to finish the task, output -1.
Sample Input

5 5
1 3 2
1 4 3
3 5 5
4 2 6
0 0

Sample Output

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


*/