CF1578L Labyrinth题解

题目链接（洛谷）

首先注意到一点：\(1\) 并不重要。即起点在哪并不是关键的。为什么？我经过一个节点时不一定要吃掉该点的糖果，而我一定要吃掉所有的糖果，所以我最初的宽度一定可以走到整个图。相当于我可以从任意节点出发。这一点说明设计状态时无需考虑起点。

我们只需要每一个糖都能吃到，即整张图是联通的。显然，我们只需要最大生成树上的边。显然，如果最大生成树上的边都走不了，通过其他边肯定也走不了。

考虑 kruskal 重构树，将一个图上问题转化成树上问题。

考虑根 \(u\) 的两棵子树，不妨记为 \(x\) 和 \(y\)。因为这里是第一个会被断开的地方，而树具有递归结构，从根节点考虑也是常见的。

我们需要将 \(x\) 和 \(y\) 内所有糖果都吃掉，则我先吃掉其中一棵子树，再通过 \(u\) 表示的整条边一定不劣。不然，我吃了一部分糖，然后穿过 \(u\) 表示的边，又需要回来。往返中必定有一次会吃完一棵子树中的糖然后穿过 \(u\) 表示的边。

考虑状态 \(f_u\) 表示走完 \(f_u\) 子树所需的最大的宽度。

我们假设先吃子树 \(x\)，则我们需要通过 \(u\) 这条边，需要满足 \(S_x + f_u \le w_u\)，其中 \(S_x\) 表示 \(x\) 的子树 \(c_i\) 和。然后我们走到 \(y\) 子树后我们还需要走完 \(y\) 的子树，所以 \(S_x +f_u \le f_y\)。

先吃子树 \(y\) 同理。所以有转移方程：

\[f_u = \max \{ \min \{ f_y -S_x,w_u - S_x\} ,\min \{ f_x -S_y,w_u - S_y\} \} \]

注意边界为叶子节点，叶子节点表示原图中的点，没有限制。

最后放一下代码。

code

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;// 重构树需要，开两倍结点
struct edge{
    int u,v,w;
    bool operator<(const edge &o)const{
        return w>o.w;
    }
}es[N];
long long c[N],f[N];//c -> S  
int n,m;
namespace KRT{
    int pre[N],bel[N];
    int ch[N][2],pj[N];
    int ncnt;
    int find(int x){return bel[x]=bel[x]==x?x:find(bel[x]);}
    void init(){
        for(int i=1;i<N;i++) bel[i]=i;
        ncnt=n;
    }
    void merge(int x,int y,int h){
        x=find(x),y=find(y);
        if(x==y) return ;
        ncnt++;
        pre[x]=pre[y]=bel[x]=bel[y]=ncnt;
        ch[ncnt][0]=x,ch[ncnt][1]=y;
        pj[ncnt]=h;
        f[ncnt]=max(min(f[y]-c[x],h-c[x]),min(f[x]-c[y],h-c[y]));
        c[ncnt]=c[x]+c[y];
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {cin>>c[i];f[i]=LONG_LONG_MAX;}//叶子结点无限制
    for(int i=1;i<=m;i++)
        cin>>es[i].u>>es[i].v>>es[i].w;
    sort(es+1,es+m+1);
    KRT::init();
    for(int i=1;i<=m;i++){
        KRT::merge(es[i].u,es[i].v,es[i].w);
    }

    if(KRT::ncnt<n*2-1||f[KRT::ncnt]<=0)printf("-1");
    else printf("%lld",f[KRT::ncnt]);
    return 0;
}