20ZR暑期联赛班 图论
P1351 联合权值
无向连通图 有 个点, 条边。点从 到 依次编号,编号为 的点的权值为 每条边的长度均为 。图上两点 的距离定义为 点到 点的最短距离。对于图 上的点对 若它们的距离为 则它们之间会产生 的联合权值。请问图 上所有可产生联合权值的有序点对中,联合权值最大的是多少? 所有联合权值之和是多少?
枚举点对一定是不行的,有一个直接的思路是枚举 中的一个,再去找另一个,可以通过,但造数据的不知道菊花图这东西。
那么可以树形 dp,这个和枚举中转点是相似的。考虑 的儿子 能找到那些点对。简单的是 与 的父亲组合,也可以从 中随意选两个。但直接做的话还会倒在菊花图下。
考虑 时 。推下去发现 的两两组合贡献为 。至此可以通过了。
P1983 车站分级
有 个火车站, 批合法的车次的运行情况。每批车次的运行情况给定了始发站,终点站,途中停靠的车站。请你给每个车站分级,满足要求:如果一趟车停靠的火车站级别为 ,那么始发站终点站之间(包括)级别 的车站都要停靠。在该条件下,回答火车站至少分成几个级别。
对于给定的 批车次,先建一个有向图,边的关系即题中的偏序关系,即为将有车停靠的站点连向所有没有车停靠的站点。如果有一条有向边 那么 必须在 的前面,这不就是拓扑排序吗?所以一些比较复杂的偏序问题,可以转换到 DAG 上进行拓扑排序 + dp 试一试。
PS,暴力建图复杂度是 的,需要信仰。考虑建立一个虚拟的中转点来优化建图,复杂度为 。
P4643 阿狸和桃子的游戏
有一张 个点 条边的图,有点权和边权。先手后手轮流染黑白两色,最后的得分是自己染的点权和 两端均为自己的颜色的边权和,双方采用最优策略,求先手的分数减去后手的分数。
不要想歪,这不可能是正儿八经的博弈论,这是联赛啊。先提一下,遇到点权和边权同时存在的题,尤其是其中一个的定义有点与众不同时,考虑能不能把点权和边权转化为一个东西,常为边权转点权。
如果一条边的两个端点同色,那么会给这两个点贡献,先让它平分给两个点。如果两个端点异色,那么两个点都没有贡献,发现平分的话抵消了。所以先把边权平分给点权,带个分数可以同时 。
那么将点权拍个序,从大到小交替贪心选即可。女少口啊。
P2680 运输计划
一株 个点的树,给你 条路径。 你需要选出一条边把边权改成 ,让这些路径长度的最大值最小。
二话不说,看到最大值最小先考虑二分。有的边已经满足条件了,不去管。那么要让其余的路径都减小到二分值及其以下,那么改的边要被其余的路径经过。假设有 条路径超限制,那么把路径上的每个边的计数器累加,最后计数器为 的取个最值。给定的是树,树上差分即可。
卡常差评。
CF1349C Orac and Game of Life
给定第 时刻的 的 矩阵。 每过一个时刻, 矩阵都会发生如下的变化:对于 行第 列的格子。若其上下左右四个方向中相邻的格子存在与其数字相同的格子,则此格子的数字在下一个时刻会取反。
有 次询问。每次问你在第 个时刻第 行第 列的格子上的数字是什么。
感觉一下,发现不断变化的位置的范围是在扩大的,而且扩大到一定程度就停下了。这样有点抽象,就拿良心的样例三试一试。
0 1 0 1 1
1 0 1 1 0
0 1 1 0 1
1 1 0 1 0
1 0 1 0 1
用 表示不会变化, 表示在不断变化。那么范围随单位时间的扩大如下
0 0 0 1 1
0 0 1 1 0
0 1 1 0 0
1 1 0 0 0
1 0 0 0 0
0 0 1 1 1
0 1 1 1 1
1 1 1 1 0
1 1 1 0 0
1 1 0 0 0
可以大胆猜测,每次 都会向四个方向扩展一次。所以一个 bfs 搞定。女少口β可。
CF209C Trails and Glades
给一张图,添加最少的边使得整张图存在一条 为起始和结束点的欧拉回路。
遇到这类有多个连通块的,往往先考虑连通块内部的贡献,再考虑连通块间的贡献。
从欧拉回路的定义入手,对于一个连通块,将度数为奇数的点两两配对,可能剩下一个。所以先去考虑连通块的连接,优先把度数为奇数的点连起来,那么其余的奇点两两配对。最多剩下一个,这个点要连出两条边。
CF1311E Construct the Binary Tree
给定 和 ,你需要构造一株 个点的二叉树,满足所有点的深度之和恰好为 。
先考虑深度最小的完全二叉树,如果 比这个深度小那么直接不可能。否则对深度进行修改,找一个叶子节点到根的链,不断把深度最大的点挂在这条链的下面。还要输出方案,啊这。
P1979 华容道
给定一个 的棋盘,只有一个空的位置。剩下的有的是障碍,有的是可移动的棋子。给定一个棋子的初始位置和目标位置,求让这个棋子移动到目标位置至少要移动几次棋子,或者回答不可能。
吐槽,这道题和图论关系不大啊。
数据范围这么小,先想爆搜,但棋子和空格可以一起走很烦。干脆 dp,设 为棋子在 ,空格在 的最少移动次数,枚举空格从哪移动过来的,如果空格与棋子相邻,还可以转移棋子。但是 会超时。
考虑空格与棋子相邻才有用,那么设 为棋子在 ,空格在 的上下左右的最少移动次数。不过这样可能没有初始状态,所以要用 bfs 预处理空格到棋子的上下左右要移动多少次即可。
CF875F Royal Questions
有 个王子 个公主,每一个公主喜欢其中两个王子,还有一个美丽度。 你需要将王子和公主配对,使得每一个公主都和自己喜欢的王子配对,并且配对的公主美丽度之和最大。
带权二分图匹配板子!哦数据范围 2e5 那没事了。
可以发现有一个公主喜欢两个王子的条件,如果构图的话,每个连通块都是树或基环树。这其实是个模板,但是联赛基础不知道 /xk。先试一试对每个连通块讨论,好像行不通,那就从零开始加边吧。
加边前先按美丽度降序排序,对于边 ,两个端点 和 可能在一个连通块中也可能不在,可能在树上也可能在基环树上,那分类讨论,要维持一棵基环树的点数一直等于边数。
- 不连通,在两棵树中:加入这条边,得到一棵新的树。
- 不连通,在一棵树和一棵基环树中:加入这条边,得到一棵基环树。
- 不连通,在两棵基环树中:无法加入。
- 连通,在一棵树中:加入这条边,树变成基环树。
- 连通,在一棵基环树中:无法加入。
是不是和生成树有点像?这个模板就叫最大生成基环树,所以用并查集维护,多加一个 bool 数组来表示是不是基环树即可。
BZOJ 2238 Mst
挂一下交题的 Link,黑暗爆炸 OJ。
给定一张图和 次询问,每次询问你删掉某条边之后最小生成树的大小。询问相互独立。
在做过删边最短路后 Link,删边最小生成树还是能做的。
先找出一棵最小生成树。
To be continued.
本文地址:https://blog.csdn.net/qq_39984146/article/details/107616023
推荐阅读