用户工具

站点工具


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