2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
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 查看代码> | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_706_div._1.1616945515.txt.gz · 最后更改: 2021/03/28 23:31 由 jxm2001
