欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

20ZR暑期联赛班 图论

程序员文章站 2022-03-16 13:07:33
P1351 联合权值无向连通图 GGG 有 nnn 个点,n−1n-1n−1 条边。点从 111 到 nnn 依次编号,编号为 iii 的点的权值为 Wi,W_{i},Wi​, 每条边的长度均为 111。图上两点 (u,v)(u, v)(u,v) 的距离定义为 uuu 点到 vvv 点的最短距离。对于图 GGG 上的点对 (u,v),(u, v),(u,v), 若它们的距离为 222 则它们之间会产生 Wu×WvW_{u} \times W_{v}Wu​×Wv​ 的联合权值。请问图 GGG 上所有可产生联...

P1351 联合权值

无向连通图 GGnn 个点,n1n-1 条边。点从 11nn 依次编号,编号为 ii 的点的权值为 Wi,W_{i}, 每条边的长度均为 11。图上两点 (u,v)(u, v) 的距离定义为 uu 点到 vv 点的最短距离。对于图 GG 上的点对 (u,v),(u, v), 若它们的距离为 22 则它们之间会产生 Wu×WvW_{u} \times W_{v} 的联合权值。请问图 GG 上所有可产生联合权值的有序点对中,联合权值最大的是多少? 所有联合权值之和是多少?1n2000001 \leq n \leq 200000

枚举点对一定是不行的,有一个直接的思路是枚举 (u,v)(u,v) 中的一个,再去找另一个,可以通过,但造数据的不知道菊花图这东西。

那么可以树形 dp,这个和枚举中转点是相似的。考虑 xx 的儿子 y1yky_1 \sim y_k 能找到那些点对。简单的是 y1yky_1 \sim y_kxx 的父亲组合,也可以从 y1yky_1 \sim y_k 中随意选两个。但直接做的话还会倒在菊花图下。

考虑 k=2k=2y1×y2=(y1+y2)2(y12+y22)2y_1 \times y_2 = \frac{{(y_1 + y_2)}^2 - ({y_1}^2+{y_2}^2)}{2}。推下去发现 y1yky_1 \sim y_k 的两两组合贡献为 (1kyi)21kyi2(\sum_{1}^k y_i)^2 - \sum_{1}^k y_i^2。至此可以通过了。

P1983 车站分级

nn 个火车站,mm 批合法的车次的运行情况。每批车次的运行情况给定了始发站,终点站,途中停靠的车站。请你给每个车站分级,满足要求:如果一趟车停靠的火车站级别为 xx,那么始发站终点站之间(包括)级别 x\ge x 的车站都要停靠。在该条件下,回答火车站至少分成几个级别。

对于给定的 mm 批车次,先建一个有向图,边的关系即题中的偏序关系,即为将有车停靠的站点连向所有没有车停靠的站点。如果有一条有向边 (u,v)(u,v) 那么 uu 必须在 vv 的前面,这不就是拓扑排序吗?所以一些比较复杂的偏序问题,可以转换到 DAG 上进行拓扑排序 + dp 试一试。

PS,暴力建图复杂度是 O(n2m)O(n^2m) 的,需要信仰。考虑建立一个虚拟的中转点来优化建图,复杂度为 O(nm)O(nm)

P4643 阿狸和桃子的游戏

Easy=NOI\text{Easy} = \text{NOI}

有一张 nn 个点 mm 条边的图,有点权和边权。先手后手轮流染黑白两色,最后的得分是自己染的点权和 ++ 两端均为自己的颜色的边权和,双方采用最优策略,求先手的分数减去后手的分数。

不要想歪,这不可能是正儿八经的博弈论,这是联赛啊。先提一下,遇到点权和边权同时存在的题,尤其是其中一个的定义有点与众不同时,考虑能不能把点权和边权转化为一个东西,常为边权转点权。

如果一条边的两个端点同色,那么会给这两个点贡献,先让它平分给两个点。如果两个端点异色,那么两个点都没有贡献,发现平分的话抵消了。所以先把边权平分给点权,带个分数可以同时 ×2\times 2

那么将点权拍个序,从大到小交替贪心选即可。女少口啊。

P2680 运输计划

一株 nn 个点的树,给你 mm 条路径。 你需要选出一条边把边权改成 00,让这些路径长度的最大值最小。

二话不说,看到最大值最小先考虑二分。有的边已经满足条件了,不去管。那么要让其余的路径都减小到二分值及其以下,那么改的边要被其余的路径经过。假设有 kk 条路径超限制,那么把路径上的每个边的计数器累加,最后计数器为 kk 的取个最值。给定的是树,树上差分即可。

卡常差评。

CF1349C Orac and Game of Life

给定第 00 时刻的 n×mn \times m0101 矩阵。 每过一个时刻,0101 矩阵都会发生如下的变化:对于 xx 行第 yy 列的格子。若其上下左右四个方向中相邻的格子存在与其数字相同的格子,则此格子的数字在下一个时刻会取反。

tt 次询问。每次问你在第 pp 个时刻第 xx 行第 yy 列的格子上的数字是什么。

感觉一下,发现不断变化的位置的范围是在扩大的,而且扩大到一定程度就停下了。这样有点抽象,就拿良心的样例三试一试。

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

00 表示不会变化,11 表示在不断变化。那么范围随单位时间的扩大如下

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

可以大胆猜测,每次 11 都会向四个方向扩展一次。所以一个 bfs 搞定。女少口β可。

CF209C Trails and Glades

给一张图,添加最少的边使得整张图存在一条 11 为起始和结束点的欧拉回路。 1n106,0m1061 \leq n \leq 10^{6}, 0 \leq m \leq 10^{6}

遇到这类有多个连通块的,往往先考虑连通块内部的贡献,再考虑连通块间的贡献。

从欧拉回路的定义入手,对于一个连通块,将度数为奇数的点两两配对,可能剩下一个。所以先去考虑连通块的连接,优先把度数为奇数的点连起来,那么其余的奇点两两配对。最多剩下一个,这个点要连出两条边。

CF1311E Construct the Binary Tree

给定 nndd,你需要构造一株 nn 个点的二叉树,满足所有点的深度之和恰好为 dd

先考虑深度最小的完全二叉树,如果 dd 比这个深度小那么直接不可能。否则对深度进行修改,找一个叶子节点到根的链,不断把深度最大的点挂在这条链的下面。还要输出方案,啊这。

P1979 华容道

给定一个 n×mn \times m 的棋盘,只有一个空的位置。剩下的有的是障碍,有的是可移动的棋子。给定一个棋子的初始位置和目标位置,求让这个棋子移动到目标位置至少要移动几次棋子,或者回答不可能。1n,m30,1q5001 \leq n, m \leq 30,1 \leq q \leq 500

吐槽,这道题和图论关系不大啊。

数据范围这么小,先想爆搜,但棋子和空格可以一起走很烦。干脆 dp,设 fi,j,x,yf_{i,j,x,y} 为棋子在 (i,j)(i,j),空格在 (x,y)(x,y) 的最少移动次数,枚举空格从哪移动过来的,如果空格与棋子相邻,还可以转移棋子。但是 O(qm2n2)O(qm^2n^2) 会超时。

考虑空格与棋子相邻才有用,那么设 fi,j,kf_{i,j,k} 为棋子在 (i,j)(i,j),空格在 (i,j)(i,j) 的上下左右的最少移动次数。不过这样可能没有初始状态,所以要用 bfs 预处理空格到棋子的上下左右要移动多少次即可。

CF875F Royal Questions

nn 个王子 mm 个公主,每一个公主喜欢其中两个王子,还有一个美丽度。 你需要将王子和公主配对,使得每一个公主都和自己喜欢的王子配对,并且配对的公主美丽度之和最大。

n,m200000n,m \leq 200000

带权二分图匹配板子!哦数据范围 2e5 那没事了。

可以发现有一个公主喜欢两个王子的条件,如果构图的话,每个连通块都是树或基环树。这其实是个模板,但是联赛基础不知道 /xk。先试一试对每个连通块讨论,好像行不通,那就从零开始加边吧。

加边前先按美丽度降序排序,对于边 (u,v)(u,v),两个端点 uuvv 可能在一个连通块中也可能不在,可能在树上也可能在基环树上,那分类讨论,要维持一棵基环树的点数一直等于边数。

  • 不连通,在两棵树中:加入这条边,得到一棵新的树。
  • 不连通,在一棵树和一棵基环树中:加入这条边,得到一棵基环树。
  • 不连通,在两棵基环树中:无法加入。
  • 连通,在一棵树中:加入这条边,树变成基环树。
  • 连通,在一棵基环树中:无法加入。

是不是和生成树有点像?这个模板就叫最大生成基环树,所以用并查集维护,多加一个 bool 数组来表示是不是基环树即可。

BZOJ 2238 Mst

挂一下交题的 Link,黑暗爆炸 OJ。

给定一张图和qq 次询问,每次询问你删掉某条边之后最小生成树的大小。询问相互独立。n50000,m,q100000n \leq 50000, m, q \leq 100000

在做过删边最短路后 Link,删边最小生成树还是能做的。

先找出一棵最小生成树。

To be continued.

本文地址:https://blog.csdn.net/qq_39984146/article/details/107616023