由于题目过多,只放几道重要的。。。
T1
• A 国有 \(n\) 座城市,编号从 \(1\) 到 \(n\),城市之间有 \(m\) 条双向道路。每一条道路对车辆都有重量限制 \(z\),简称限重。
• 现在有 \(q\) 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。
• \(1 ≤ n \leq 10^4\),\(1 ≤ m \leq 5 \cdot 10^4\),\(1 ≤ q ≤ 3 \cdot 10^4\),\(0 ≤ z ≤ 10^5\)。
Solution
• 实现 \(x\) 到 \(y\) 的所有路经中,路径上边的最小值最大。
• 容易想到把图转化为最大生成树,树上两点的路径就是所有路径中,最小值最大的路径。
• 树上两点间的最小路径值,容易想到用倍增计算。
T2
• 有一个树形的水系,由 \(N−1\) 条河道和 \(N\) 个交叉点组成。
• 每条河道都有一个容量,连接 \(x\) 与 \(y\) 的河道的容量记为 \(c(x, y)\)。
• 有一个节点是整个水系的发源地,可以源源不断地流出水,我们称之为源点。
• 除了源点之外,树中所有度数为 \(1\) 的节点都是入海口,可以吸收无限多的水,我们称之为汇点。
• 流入该点的河道水量之和等于从该点流出的河道水量之和。
• 整个水系的流量就定义为源点单位时间发出的水量。
• 在流量不超过河道容量的前提下,求哪个点作为源点时,整个水系的流量最大,输出这个最大值。
• \(N \leq 2 \cdot 10^5\),数据保证结果不超过 \(2^{31}−1\)。
Solution
• 定义 \(f_i\) 表示以 \(i\) 为根的子树的最大流量。
\[ f_n = \sum_ {v \in son(u)} \begin{cases} \min (f_v, w(u, v)) & deg_v > 1 \\\\ w(u, v) & deg_v = 1 \end{cases}\]• 接下来考虑换根 \(dp\)
• 对于原本以 \(u\) 为根,转为以 \(v\) 为根,分类讨论。
- 如果 \(deg_u = 1\),\(f_v += w(u, v)\)。
- 如果 \(deg_v = 1\),\(f_v = \min(fu − w(u, v),w(u, v))\)。
- 否则,\(f_v += \min(fu − \min(fv ,w(u, v)),w(u, v))\)。
T3
题目
• 一所学校前一段时间买了第一台计算机(所以这台计算机的 \(ID\) 是 \(1\))。
• 近年来,学校又购买了 \(N−1\) 台新计算机。
• 每台新计算机都与之前买进的计算机中的一台建立连接。
• 现在请你求出第 \(i\) 台计算机到距离其最远的计算机的电缆长度。
• \(1 ≤ N ≤ 10000\), 电缆总长度不超过 \(10^9\)。
Solution
• 先考虑如何计算第 \(1\) 台计算机到距离其最远的计算机的电
缆长度。
• 以第 \(1\) 台电脑为根,计算树的最大深度即为答案。
• 计算每个点的答案,还是换根 \(dp\)。。。
• 下文中,以 \(son_u\) 表示 \(u\) 的重儿子,\(d1_u\) 表示以 \(u\) 为根的子树的最大深度,\(d2_u\) 表示以 \(u\) 为根的子树的次大深度。
• 原本以 \(u\) 为根,换到以 \(v\) 为根,分类讨论。