CF1578L 题解

· · 题解

题意

一个无向连通图，边有宽度，点上有糖，糖吃完会使人变胖（即宽度增加）。

人从 1 节点出发，任意移动，但只能走过宽度不超过自身宽度的边，走到点上可以选择吃掉该点上的糖果，每个糖果只能吃一次。

求出要吃完所有糖果，人的初始宽度的最大值，如果无论如何都吃不完，输出 -1。

题解

首先解决这样一个问题：如果从点 a 走到点 b，人的最大宽度可以是多少，即找到一条从 a 到 b 的路径，使得它所经过的边的宽度最小值最大。

这是一个经典问题（P1967 货车运输），根据题解我们知道，答案应该是建立最大生成树后，a, b 两点之间边权最小值。当然你也可以用 kruskal 算法流程推出这一结论：这个算法实际上就是在用尽可能大的边让 a, b 联通。

问题现在转化为一个树上问题，看上去简单了很多。

当人在不停的吃糖时，有些边就会因为人宽度的增加而断掉，这对于一颗树而言是毁灭性的，因为这样它就不再联通了，你也不可能吃完所有糖了，除非，这条边断开的时候，被割下来的那一棵子树早就被你吃完了。

第一条断掉的边一定是宽度最小的那一条，我们设它连接的是 u,v 两点，宽度为 w。设这条边断掉之后，u, v所对应的那棵树（下文简称树 u，树 v）的糖果值总和分别为 s_u, s_v。

不妨设人先吃完了树 u 的所有糖果，然后我们证明一个结论：在一开始吃完树 u 的全部节点一定不劣于其他决策。考虑存在一种解法，使得吃完树 u，吃掉了些树 v 的糖果，那么由于之后还能从 (u, v, w) 返回，则当前宽度一定不超过 w，也就不超过树上的任意一条边的宽度，因此以什么顺序吃掉这些糖果都不会有问题，换成先吃完树 u 并不会变劣。

吃完了树 u，我们惊讶地发现只要得到原问题在树 v 上的答案 x_v，那么答案就是 \min\{x_v-s_u, w-s_u\}。先吃树 v 也是同理，因此答案是 \max\{\min\{x_v-s_u, w-s_u\}, \min\{x_u-s_v, w-s_v\}\}，最后如果发现答案非正，则输出 -1。

还剩两个小问题，第一是初始节点是 1 而不是 u 或 v，能不能从 1 走到它们两个呢？由于最终答案不可能大于 w（不然一开始树就不联通了），所以一开始是可以在整棵树上随便走的。

第二是如何在递归求解的时候快速得到那一棵子树中宽度最小的边？在建最大生成树时建立 kruskal 重构树，那么一条边的左右儿子就是它左右两棵子树的宽度最小的边的编号，这是由于 kruskal 算法先连接边权大的边，那么重构树的子树的根一定是最后连接的边，就是边权最小的。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
const int N = 200005;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, c[N];
struct Edge
{
    int x, y, w;
} E[N];
int fa[N];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
    return;
}
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
ll f[N], sum[N];//f,x分别对应上文中的x,s
int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", c + i);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d%d", &E[i].x, &E[i].y, &E[i].w);
    std::sort(E + 1, E + 1 + m, [](Edge a, Edge b) -> bool
              { return a.w > b.w; });
    init(n + m);
    int rt = 0;
    for (int i = 1; i <= n;++i)
        f[i] = inf, sum[i] = c[i];//单个点作为树的边界情况的处理
    for (int i = 1; i <= m; ++i) //建立kruskal重构树
    {
        int x = E[i].x, y = E[i].y;
        if ((x = find(x)) != (y = find(y)))
        {
            int k = i + n;
            fa[x] = fa[y] = k;
            rt = k;//rt是最后一条被加入生成树的边，即重构树的根
            ll w = E[i].w; 
            f[k] = std::max(std::min(w - sum[x], f[y] - sum[x]),
                            std::min(w - sum[y], f[x] - sum[y]));
            sum[k] = sum[x] + sum[y];
            //这里是递归求解的过程改成了递推
            //x,y分别是k的左右儿子
        }
    }
    printf("%lld\n", f[rt] <= 0 ? -1ll : f[rt]);
    return 0;
}