这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1 [2021/03/28 23:31] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1 [2021/03/29 10:28] (当前版本) jxm2001 [题解] |
||
---|---|---|---|
行 225: | 行 225: | ||
==== 题解 ==== | ==== 题解 ==== | ||
- | 令 $p_0=n+1$,将每个点向左边第一个 $p_j\gt j$ 的元素连一条边。 | + | 接下来对原图,设每个点连出一条费用为 $a_i$ 的边和费用为 $b_i$ 的边指向对应顶点,同时 $a_0=0,b_0=\infty,p_0=n+1$。 |
- | 不难发现可以得到一棵树,且设当前处于结点 $i$,则如果花费 $a_i$ 后接下来一定会遍历 $i$ 的所有儿子结点。 | + | 于是原题转化为求从 $0$ 号结点到终点的最短路径。 |
- | 如果花费 $b_i$ 则将跳过 $i$ 所在的子树。 | + | 将每个点向左边第一个 $p_j\gt j$ 的元素连一条边,不难发现可以得到一棵树,其中 $0$ 为根节点。 |
- | 设 $\text{dp}(i)$ 表示在结点 $i$ 选择花费 $a_i$,离开 $i$ 的整个子树的总费用。 | + | 若当前处于结点 $i$。如果走 $a$ 边则接下来一定会遍历 $i$ 在树上的所有儿子结点,如果走 $b$ 边则将跳过 $i$ 所在的子树的所有结点。 |
- | 设当前轮操作中选择在结点 $i$ 花费 $a_i$ 的结点集合为 $T$,$a_0=b_0=0$,此时总费用为 | + | 设最短路中所有 $a$ 边的起点构成的集合为 $T$,此时总费用为 |
$$ | $$ | ||
行 239: | 行 239: | ||
$$ | $$ | ||
- | 设 $c_i=a_i-b_i+\sum_{j\in \text{child}(i)}b_j$,则上式化简为 $\sum_{i\in T}c_i$。 | + | 设 $c_i=a_i-b_i+\sum_{j\in \text{child}(i)}b_j,c_0=\sum_{i\in \text{child}(0)}b_i$,则上式化简为 $\sum_{i\in T}c_i$。 |
设 $\text{dp}(i)$ 表示 $i\in T$ 时 $T$ 集合中 $i$ 的子树结点的 $c_i$ 和的最小值,则有状态转移方程 | 设 $\text{dp}(i)$ 表示 $i\in T$ 时 $T$ 集合中 $i$ 的子树结点的 $c_i$ 和的最小值,则有状态转移方程 | ||
行 250: | 行 250: | ||
于是 $T$ 一定是连通集且 $S$ 的父结点一定属于 $T$,设 $H$ 集合为满足该限制的最小集合,于是最小费用为 | 于是 $T$ 一定是连通集且 $S$ 的父结点一定属于 $T$,设 $H$ 集合为满足该限制的最小集合,于是最小费用为 | ||
- | |||
- | $$ | ||
- | \sum_{i\in H}(c_i+\sum_{j\not\in H,j\in \text{child}(i)}\min(\text{dp}(j),0))=\sum_{i\in H}(\text{dp}(i)-\sum_{j\in H,j\in \text{child}(i)}\min(\text{dp}(j),0))=\text{dp}(0)+\sum_{i\in H}(\text{dp}(i)-\min(\text{dp}(i),0)) | ||
- | $$ | ||
$$ | $$ | ||
行 259: | 行 255: | ||
\sum_{i\in T}c_i&=\sum_{i\in H}\left(c_i+\sum_{j\not\in H,j\in \text{child}(i)}\min(\text{dp}(j),0)\right) \\ | \sum_{i\in T}c_i&=\sum_{i\in H}\left(c_i+\sum_{j\not\in H,j\in \text{child}(i)}\min(\text{dp}(j),0)\right) \\ | ||
&=\sum_{i\in H}\left(\text{dp}(i)-\sum_{j\in H,j\in \text{child}(i)}\min(\text{dp}(j),0)\right)\\ | &=\sum_{i\in H}\left(\text{dp}(i)-\sum_{j\in H,j\in \text{child}(i)}\min(\text{dp}(j),0)\right)\\ | ||
- | &=\text{dp}(0)+\sum_{i\in H}(\text{dp}(i)-\min(\text{dp}(i),0))\\ | + | &=\text{dp}(0)+\sum_{i\neq 0,i\in H}(\text{dp}(i)-\min(\text{dp}(i),0))\\ |
- | &=\text{dp}(0)+\sum_{i\in H}\max(\text{dp}(i),0) | + | &=\text{dp}(0)+\sum_{i\neq 0,i\in H}\max(\text{dp}(i),0) |
\end{split}\end{equation} | \end{split}\end{equation} | ||
$$ | $$ | ||
- | 接下来考虑如何维护 $H$ 集合即可,将点权转移为到父结点的边权,发现可以类似虚树 $\text{dp}$ 的方式维护最小连通集合。 | + | 接下来考虑如何维护 $H$ 集合即可,将点权转移为到连向父结点的边权,发现可以用类似构建虚树 $\text{dp}$ 的方式维护最小连通集合。 |
- | + | ||
- | 另外由于本题建图的特殊性,导致 $\text{dfs}$ 序可以等于结点编号。 | + | |
- | 时间复杂度 $O(n\log n)$。 | + | 另外由于本题建树的特殊性,使得可以直接让 $\text{dfs}$ 等于结点编号。时间复杂度 $O(n\log n)$。 |
<hidden 查看代码> | <hidden 查看代码> |