题解 - HDU3586 Information Disturbing

zimindaada · 2020-02-09 12:11:41 · 个人记录

题面

//dp[u] 表示 u 的叶子和 u 全部分离所需消耗的最小能量
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int inf = 0x3f3f3f;
int n, m;

int last[maxn], ecnt;
struct edge{int y, w, gg;} e[maxn<<1];
inline void addedge(int x, int y, int w){
    e[ecnt].y = y; e[ecnt].w = w; e[ecnt].gg = last[x];
    last[x] = ecnt++;
}
inline void eclr(){
    memset(last, -1, sizeof(last));
    ecnt = 0;
}

int dp[maxn];
void dfs(int x, int fa, int lim){
    dp[x] = 0;
    bool have_son = 0; int y;
    for(int i = last[x]; i != -1; i = e[i].gg){
        y = e[i].y; 
        if(y == fa) continue;
        have_son = 1;
        dfs(y,x,lim);
        //如果uv边小于lim，那么可以选择切uv边或让儿子v进行选择
        if(e[i].w <= lim) dp[x] += min(e[i].w,dp[y]); 
        //如果大于lim，那就只能让儿子操作
        else dp[x] += min(inf,dp[y]);
    }
    if(have_son == 0) dp[x] = inf; //叶子不存在和叶子分离的状态
}

bool check(int uplim){
    for(int i = 1; i <= n; ++i) dp[i] = inf;
    dfs(1,-1,uplim);
    return dp[1] <= m;
    //题目要求，
}

signed main(){
    while(scanf("%d%d",&n,&m) && (n||m)){
        eclr();

        int xx, yy, zz;
        for(int i = 1; i < n; ++i){
            scanf("%d%d%d",&xx,&yy,&zz);
            addedge(xx,yy,zz); addedge(yy,xx,zz);
        }
        //二分查找答案
        int l = 1, r = m, ans = -1;
        while(l <= r){
            int mid = (l+r)>>1;
            if(check(mid)) {//对当前mid进行dfs，看是不是答案
                ans = mid;
                r = mid-1;
            }else l = mid+1;
        }

        printf("%d\n", ans);
    }
    return 0;
}