题解 | #吉吉王国#

题目想法

这是Rinne Loves Edges的扩展版, 依然是剪掉一些路径从而达到题目要求, 但多了一重限制, 不过不影响核心思路

题目要求

要剪去所有叶子结点路径(可以剪去叶子结点, 也可以剪去叶子结点的某个根结点), 并且总权值要小于等于m. 而题目要求的结果为 求剪去所有叶子结点且总权值小于等于m的所有方案中, 最长边最短的值

题目思路

二分求最优解, 典型二分思路, 每次二分最长边的值, 即最长边为x时, 剪去叶子结点总权值是否小于等于m, 若满足条件则更新res答案值
注意如果最大值INF设为0x3f3f3f3f, 要用到long long, 不然会爆, 所以我的代码中设为的1e7 + 10, 因为懒得改long long了

代码实现

#include <bits/stdc++.h>

#define INF 1e7 + 10

using namespace std;

const int N = 1010, M = N * 2;

int n, m;
int e[M], w[M], ne[M], h[N], idx;
int f[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

void dfs(int u, int father, int x)
{
    bool is_leaf = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs(j, u, x);
        is_leaf = false;
        f[u] += min(f[j], w[i] > x ? f[j] : w[i]);
    }
    if (is_leaf) f[u] = INF;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c); 
    }

    int l = 0, r = 1e6 + 10;
    int res = 0;
    while (l < r)
    {
        int mid = l + r >> 1;
        memset(f, 0, sizeof f);
        dfs(1, -1, mid);
        if (f[1] <= m) r = mid, res = r;
        else l = mid + 1;
    }

    if (!res) puts("-1");
    else printf("%d\n", res);

    return 0;
}