2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_2 [2023/07/23 20:12] coldwinds |
2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_2 [2023/07/23 20:14] (当前版本) coldwinds |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| ===B=== | ===B=== | ||
| - | **树剖+线段树+网络流** | + | **树剖+线段树+网络流（最大权闭合子图）** |
| 给定一棵n个节点的树，有边权（维护成本），给定m组顶点，代表一条线路，同时给出了该线路带来的利润。可以删除树上的边，以及放弃若干条线路，求：最大利润。 | 给定一棵n个节点的树，有边权（维护成本），给定m组顶点，代表一条线路，同时给出了该线路带来的利润。可以删除树上的边，以及放弃若干条线路，求：最大利润。 | ||
| 行 13: | 行 13: | ||
| 由于点的数量为1e4，最坏情况有1e8条边，无法直接建图，可以用线段树优化建图。对给出的树进行树链剖分，将每条线路的路径转化为若干连续区间，再使用线段树优化对区间的连边(若区间[L,R]在线段树上用一个节点维护，则直接将边连到改节点，不需要连到叶节点)。优化过的图，点数为5n+m=6e4，边数为5n+m(1+logn)=2e5。 | 由于点的数量为1e4，最坏情况有1e8条边，无法直接建图，可以用线段树优化建图。对给出的树进行树链剖分，将每条线路的路径转化为若干连续区间，再使用线段树优化对区间的连边(若区间[L,R]在线段树上用一个节点维护，则直接将边连到改节点，不需要连到叶节点)。优化过的图，点数为5n+m=6e4，边数为5n+m(1+logn)=2e5。 | ||
| + | |||
| + | **AC代码** | ||
| <code> | <code> | ||
2023-2024/teams/ikun_is_coding/2023_牛客暑期多校训练营_2.1690114331.txt.gz · 最后更改: 2023/07/23 20:12 由 coldwinds
