题解

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences 题解 Author: Yuyi 题目分析与推导过程 这道题和之前的《P7771 欧拉路径》可以说是“同源兄弟”，只不过这一次我们的图变成了 无向图 （且存在重边），要求输出的同样是字典序最小的欧拉路径。 判定无向图欧拉路径的起点规则： 在无向图中，我们不需要分别统计入度和出度，…

P7771 【模板】欧拉路径 题解 Author: Yuyi 题目分析与推导过程 这道题是一道非常经典的图论模板题：求有向图的欧拉路径，并且要求字典序最小。 欧拉路径 是指在一个图中，恰好经过每一条边一次的路径。 判定欧拉路径存在性的核心条件： 对于有向图，要存在欧拉路径，所有的点必须严格满足以下两种情况之一： 1. 欧拉回路（起点和终点重合） ：图中所有顶…

UVA10369 Arctic Network 题解 Author: Yuyi 题意分析 本题完全就是 P1991 无线通讯网 的国际原版！题目意思、条件限制甚至数据范围和核心要求都如出一辙：在 $P$ 个坐标点中连边，拥有 $S$ 个能够无视距离的“卫星频道”。我们要找到一个最小的通用收发器距离 $D$，使得在这 $D$ 距离内连边后，借助这 $S$ 个卫…

U92652 【模板】kruskal重构树 题解 Author: Yuyi 题意分析 题目要求在一张无向图中，对于 $Q$ 组询问 $(x,y)$，求出所有从 $x$ 到 $y$ 的路径中， 单条边权最大值的最小值 。如果两点不连通，则输出 1 。 这又是最小生成树家族里的一个经典模板—— Kruskal 重构树 ！ 它的思想非常巧妙：在普通的 Kruska…

P13514 [KOI 2025 1] 干草堆 题解 Author: Yuyi 题意分析 题目要求我们在前 $X$ 个干草堆中，选出最少数量的干草堆，使得它们的防御力总和大于等于箭的力量 $P$。 由于我们的目标是“最小化”干草堆的数量，根据贪心策略，我们显然应该 优先选择防御力最大的干草堆 。 也就是说，对于每次查询 $(X, P)$，其实质就是：把前 $…

P13513 [KOI 2025 1] 釜山观光 题解 Author: Yuyi 题意分析 两人在釜山观光 $N$ 天。每天可以选择游玩或者不游玩。 有四种票：1日票、3日票、5日票（均为单人票），以及4日双人组合票。 要求在两人所有“游玩”的日子里，都必须持有有效的票。 票的有效期可以重叠，也可以超出 $N$ 天。价格的大小关系也不一定遵循天数越长越贵的规…

P13512 [KOI 2025 1] 稻草人 题解 Author: Yuyi 题意分析 题目的核心在于：一支初始力量为 $P$ 的箭，每穿过一个防御力为 $A k$ 的稻草人，力量减少 $A k$（如果 $P \le A k$ 则直接停止）。这等价于：要使箭停止，沿途经过并生效的稻草人防御力之和必须大于等于 $P$。 对于每个位置 $i$，目标是从前 $i…

P4047 [JSOI2010] 部落划分 题解 Author: Yuyi 题意分析 题目给定 $N$ 个野人的居住点，要求我们将这 $N$ 个点划分成 $K$ 个部落（连通块）。 我们的目标是：让这 $K$ 个部落之间，靠得最近的两个部落的距离 尽可能远 。输出这个最近的距离。 这其实是聚类算法里最经典的 最短距离聚类（Single linkage clu…

P3366 【模板】最小生成树 题解 Author: Yuyi 题意分析 给定一个 $N$ 个节点、$M$ 条边的无向图，要求找到连通所有节点的最小生成树（MST），即选出 $N 1$ 条边使得图连通且边权之和最小。如果图本身就不连通，则输出 orz 。 正解推导过程 最小生成树最经典的算法是 Kruskal 算法 ，它本质上是贪心与并查集的完美结合。 1.…

P2872 [USACO07DEC] Building Roads S 题解 Author: Yuyi 题意分析 本题给定 $N$ 个点的坐标，并且告知图里已经提前建好了 $M$ 条边。题目要求我们在此基础上额外再连一些边，让所有的 $N$ 个点连通，并且要求 额外添加的边权（距离）总和最小 。 这依然是一道标准的 Kruskal 最小生成树 ，唯一的区别在…

P2504 [HAOI2006] 聪明的猴子 题解 Author: Yuyi 题意分析 猴子想要在所有的树冠上觅食，就意味着它必须要能在所有树之间来回穿梭。换句话说，对于这只猴子而言，它能够到达的那些树必须构成一个 完整的连通图 。 猴子能跳跃的最大距离是固定的，如果这个最大距离大于等于将所有树连通所需的 最小的“最大跳跃跨度” ，那么这只猴子就能存活。 这…

P2482 [SDOI2010] 猪国杀——大模拟题解 Author: Yuyi 一、先理解题意：这不是博弈，而是确定性模拟 这道题看起来像一局复杂的卡牌游戏，但题目已经规定了每只猪在任何情况下的行动准则，因此我们不需要搜索最优策略，也不需要做博弈论。 我们真正要做的是： 按照题目给定的优先级，完整、准确地重放整局游戏，直到一方满足胜利条件。 游戏中的每一个…

P2330 [SCOI2005] 繁忙的都市 题解 Author: Yuyi 题意分析 题目的核心要求翻译过来就是三句话： 1. 保证图连通； 2. 在连通的情况下，选取的边数最少（显然就是 $N 1$ 条边，也就是一棵生成树）； 3. 在所有生成树中，使得边权最大的那条边的权值 尽量小 。 这其实就是求图的 瓶颈生成树 （Bottleneck Spanni…

P2121 拆地毯 题解 Author: Yuyi 题意分析 题目给定 $N$ 个点和 $M$ 条带有美丽度（边权）的无向边。组织者要求保留 至多 $K$ 条边 ，并且这 $K$ 条边连起来 不能有环 ，同时要求保留下来的边权之和最大。 不能有环，其实就是森林或者树的结构；要边权之和最大，这毫无疑问就是 最大生成树（最大生成森林） 的模型！ 由于题目只要求保…

P1991 无线通讯网 题解 Author: Yuyi 题意分析 题意可以转化为：给定 $P$ 个哨所（可以看作平面上的 $P$ 个点），我们要在任意两点之间连一条边，边的权值为这两点之间的欧几里得距离。 现在我们手里有 $S$ 个“卫星电话”。拥有卫星电话的哨所之间互相通信是“免费”的（距离不受限）。这意味着这 $S$ 个分配了卫星电话的哨所，等价于允许整…

P1967 [NOIP 2013 提高组] 货车运输 题解 Author: Yuyi 题意分析 题意是要我们求：在 $x$ 到 $y$ 的所有连通路径中， 单条边权的最小值尽可能大 。如果两人压根不连通，输出 1 。 我们之前已经解决过“U92652 Kruskal重构树模板”和“P4768 归程”，这题和它们如出一辙，只不过把“求最小”变成了“求最大”而已…

P1396 营救 题解 Author: Yuyi 题意分析 妈妈在 $s$ 区，小明在 $t$ 区。给出一张无向图（可能有重边），每条边有一个“拥挤度”。我们要求出一条从 $s$ 走到 $t$ 的路径，使得这条路径上 拥挤度的最大值 尽可能小。 这是图论中极其经典的 “瓶颈路径” （Bottleneck Path）问题。其实这个问题跟最小生成树（MST）同宗…

P1195 口袋的天空 题解 Author: Yuyi 题意分析 题意很唯美，但本质依然是赤裸裸的图论模型：有 $N$ 朵云（点）和 $M$ 种连接关系（无向边）。我们想要把这些云朵连成恰好 $K$ 个棉花糖（连通块）。 每一个棉花糖至少包含一朵云。题目要求我们挑选一些边使得它们连通，并且花费的总代价（边权之和）最小。 如果是要把 $N$ 个点连成 $1$ …

P1194 买礼物 题解 Author: Yuyi 题意分析 明明要买 $B$ 样东西，原价都是 $A$ 元。但如果买了 $I$ 再买 $J$，就可以享受 $K {I,J}$ 的优惠价。 我们要让花的最少，这就等价于图论中经典的“ 超级源点 + 最小生成树 ”模型！ 我们可以假设存在一个编号为 $0$ 的“原价商店”（超级源点）： 1. 0 号点连向每一个物…

P4768 [NOI2018] 归程 题解 Author: Yuyi 题意分析 题目的要求很清晰：Yazid 要从节点 $v$ 回到节点 $1$。前半段他可以坐车，条件是经过的边的海拔必须严格大于水位线 $p$；一旦他下了车，剩下的路就只能步行，而且要求步行距离最短。 也就是说，在给定的水位线 $p$ 下，Yazid 坐车可以在“海拔 $ p$ 的子图”里随…