2020-2021:teams:farmer_john:2020暑假精选题目:图论
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:图论 [2020/09/04 20:10] jjleo [题意] |
2020-2021:teams:farmer_john:2020暑假精选题目:图论 [2020/09/04 20:19] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| ====题解==== | ====题解==== | ||
| - | 首先找到所有边双联通分量将其缩点，可以证明每一个边双都可以给边定向从而形成强连通分量，因此每一个边双内部不用考虑边的定向问题。现在原图转化为了一棵树，下面所说的关键点指包含关键点的边双。以一个关键点为根，将所有叶子节点为非关键点的点都向上缩，权值进行叠加，因为它们只需要将边定向为向上就可以到达关键点，这样可以简化后续讨论。现在我们所有叶子节点均为关键点，那么所有能到达关键点的 | + | 首先找到所有边双联通分量将其缩点，可以证明每一个边双都可以给边定向从而形成强连通分量，因此每一个边双内部不用考虑边的定向问题。 |
| + | |||
| + | 现在原图转化为了一棵树，下面所说的关键点指包含关键点的边双。以一个关键点为根，将所有叶子节点为非关键点的点都向上缩，权值进行叠加，因为它们显然定向为上才有意义，因此可以锁到距离最近的关键点，这样可以简化后续讨论。 | ||
| + | |||
| + | 现在我们所有叶子节点均为关键点，那么能被所有关键点到达的点一定组成一个连通块，连通块内部所有边无向，其它边均被定向。因此我们可以使用树形dp解决下面的问题，设$f_i$为以$i$为根的子树中包含点$i$的连通块的最大权值，转移为$$f_i=C_i+\sum_{{j \in son_i}}\max(f_j-w,0)$$其中$w$为对应的边权，$C_i$为缩点后的总权值，那么单次dp中对于根节点最终所求的答案为$f_{root}$。 | ||
| + | |||
| + | 我们最后再进行一次换根dp，即可以每个点为根求出最终的答案。注意到因为第一次我们选的关键点为根，所以换根过程中始终满足所有叶子节点均为关键点这一条件。 | ||
2020-2021/teams/farmer_john/2020暑假精选题目/图论.1599221433.txt.gz · 最后更改: 2020/09/04 20:10 由 jjleo
