![P15895 [TOPC 2025] One-Way Abyss 题解](images/news1.jpg)
P15895 [TOPC 2025] One-Way AbyssLink: https://www.luogu.com.cn/problem/P15895题目描述米蒂是一位勇敢的冒险家正在探索一个名为“深渊”的神秘地下洞穴系统。深渊由n nn条垂直的竖井和m mm条水平的隧道组成。每条隧道恰好连接同一深度上的两条竖井。所有m mm条隧道的深度各不相同而且令人惊奇的是每条隧道的正中央都有一份宝藏米蒂可以选择任意一条竖井作为起点。他从所选竖井的顶部开始向下移动并遵循以下规则他只能向下移动不允许向上移动。每当遇到一条水平隧道时他必须立即进入这条隧道并到达与之相连的另一条竖井。一旦进入一条水平隧道就无法原路返回。这些隧道中的宝藏具有不同的价值。米蒂希望尽可能多地收集宝藏。请帮助他计算从某条竖井出发时他最多能收集到的宝藏总价值。输入格式每个测试点包含多个测试用例。第一行包含测试用例的数量t tt接下来是每个测试用例的描述。每个测试用例的第一行包含两个整数n nn和m mm分别表示竖井的数量和水平隧道的数量。接下来的m mm行每行包含三个整数x xx、y yy和v vv表示一条位于某个深度的水平隧道连接编号为x xx和y yy的两条竖井且隧道内包含一份价值为v vv的宝藏。水平隧道按照从上到下的顺序给出这意味着不会有两条水平隧道处于同一深度。输出格式对于每个测试用例输出一个整数表示米蒂能够收集到的最大宝藏总价值。输入输出样例 #1输入 #11 3 3 1 2 3 2 3 4 1 3 9输出 #116输入输出样例 #2输入 #22 5 8 1 4 5 1 3 4 1 3 2 1 3 9 2 4 1 1 3 2 2 3 0 1 5 6 7 2 5 6 16 5 7 4输出 #228 20说明/提示1 ≤ t ≤ 20 1 \le t \le 201≤t≤201 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times 10^51≤n≤2×1050 ≤ m ≤ 2 × 10 5 0 \le m \le 2 \times 10^50≤m≤2×1051 ≤ x y ≤ n 1 \le x y \le n1≤xy≤n0 ≤ v ≤ 10 9 0 \le v \le 10^90≤v≤109保证所有测试用例的n nn之和不超过2 × 10 5 2 \times 10^52×105。保证所有测试用例的m mm之和不超过2 × 10 5 2 \times 10^52×105。翻译由 DeepSeek V3.2 完成Solution1. 题意一个下落游戏沿着竖线下落遇到横线必须顺着横线移步到另一条竖线并获得这条横线里的价值求到达底部时的最大总价值。2. 分析由于不存在位于相同高度的横线因此横线自上而下依次排列可记为第1 , 2 , ⋯ 1,2,\cdots1,2,⋯层。设f ( i , j ) f(i,j)f(i,j)表示到达第i ii层时处于j jj号矿井时的价值那么根据每行输入的( x , y , v i ) (x,y,v_i)(x,y,vi)表示的连接关系容易发现可能有下面两种操作从y yy号矿井移步到x xx号矿井获得v i v_ivi的价值从x xx号矿井移步到y yy号矿井同样是获得v i v_ivi的价值。如此一来能得到下面两个相互交织的递推方程组{ f ( i , x ) f ( i − 1 , y ) v i f ( i , y ) f ( i − 1 , x ) v i \begin{cases} f(i,x) f(i-1,y) v_i \\ f(i,y) f(i-1,x) v_i \end{cases}{f(i,x)f(i−1,y)vif(i,y)f(i−1,x)vi最开始累计的价值为零因此初始条件是∀ t ∈ { 1 , 2 , ⋯ , n } , f ( 0 , t ) 0 \forall t \in \{1,2,\cdots, n\}, \quad f(0,t) 0∀t∈{1,2,⋯,n},f(0,t)0由于数据是2 × 10 5 2\times 10^52×105的数据规模因此O ( n 2 ) O(n^2)O(n2)的二维数组存所有的f ( i , j ) f(i,j)f(i,j)在空间复杂度上显然过不去需要考虑滚动优化将空间复杂度打到O ( n ) O(n)O(n)数组里只保留最近的最优即可。因为求最优解时只需要用最近一步迭代的结果继续往后推更早的用不到了。3. 代码usingSystem;classP15895{staticvoidMain(){inttConvert.ToInt32(Console.ReadLine());while(t--0){varnmConsole.ReadLine().Split();intnConvert.ToInt32(nm[0]);intmConvert.ToInt32(nm[1]);long[]fnewlong[n1];longresult0;for(inti0;im;i){varxyvConsole.ReadLine().Split();intxConvert.ToInt32(xyv[0]);intyConvert.ToInt32(xyv[1]);longvConvert.ToInt64(xyv[2]);longtmpxf[x],tmpyf[y];f[x]tmpyv;f[y]tmpxv;}for(inti1;in;i){if(f[i]result)resultf[i];}Console.WriteLine(result);}}}4. 轶事利用 C# 的托管等机制可以免去“多测不清空零分两行泪”以及内存泄漏的苦恼本题的模型其实是起源于东亚的一种梯子游戏 [1]。游戏结果完全仅由横线的排布决定无任何运气成分。换句话说出口和入口的对应关系其实就是一个已经定死的1 ∼ n 1\sim n1∼n的全排列。反映到这道题上选择一个入口后总共拿到多少奖励已经是板上钉钉的事。
P15895 [TOPC 2025] One-Way Abyss 题解
P15895 [TOPC 2025] One-Way AbyssLink: https://www.luogu.com.cn/problem/P15895题目描述米蒂是一位勇敢的冒险家正在探索一个名为“深渊”的神秘地下洞穴系统。深渊由n nn条垂直的竖井和m mm条水平的隧道组成。每条隧道恰好连接同一深度上的两条竖井。所有m mm条隧道的深度各不相同而且令人惊奇的是每条隧道的正中央都有一份宝藏米蒂可以选择任意一条竖井作为起点。他从所选竖井的顶部开始向下移动并遵循以下规则他只能向下移动不允许向上移动。每当遇到一条水平隧道时他必须立即进入这条隧道并到达与之相连的另一条竖井。一旦进入一条水平隧道就无法原路返回。这些隧道中的宝藏具有不同的价值。米蒂希望尽可能多地收集宝藏。请帮助他计算从某条竖井出发时他最多能收集到的宝藏总价值。输入格式每个测试点包含多个测试用例。第一行包含测试用例的数量t tt接下来是每个测试用例的描述。每个测试用例的第一行包含两个整数n nn和m mm分别表示竖井的数量和水平隧道的数量。接下来的m mm行每行包含三个整数x xx、y yy和v vv表示一条位于某个深度的水平隧道连接编号为x xx和y yy的两条竖井且隧道内包含一份价值为v vv的宝藏。水平隧道按照从上到下的顺序给出这意味着不会有两条水平隧道处于同一深度。输出格式对于每个测试用例输出一个整数表示米蒂能够收集到的最大宝藏总价值。输入输出样例 #1输入 #11 3 3 1 2 3 2 3 4 1 3 9输出 #116输入输出样例 #2输入 #22 5 8 1 4 5 1 3 4 1 3 2 1 3 9 2 4 1 1 3 2 2 3 0 1 5 6 7 2 5 6 16 5 7 4输出 #228 20说明/提示1 ≤ t ≤ 20 1 \le t \le 201≤t≤201 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times 10^51≤n≤2×1050 ≤ m ≤ 2 × 10 5 0 \le m \le 2 \times 10^50≤m≤2×1051 ≤ x y ≤ n 1 \le x y \le n1≤xy≤n0 ≤ v ≤ 10 9 0 \le v \le 10^90≤v≤109保证所有测试用例的n nn之和不超过2 × 10 5 2 \times 10^52×105。保证所有测试用例的m mm之和不超过2 × 10 5 2 \times 10^52×105。翻译由 DeepSeek V3.2 完成Solution1. 题意一个下落游戏沿着竖线下落遇到横线必须顺着横线移步到另一条竖线并获得这条横线里的价值求到达底部时的最大总价值。2. 分析由于不存在位于相同高度的横线因此横线自上而下依次排列可记为第1 , 2 , ⋯ 1,2,\cdots1,2,⋯层。设f ( i , j ) f(i,j)f(i,j)表示到达第i ii层时处于j jj号矿井时的价值那么根据每行输入的( x , y , v i ) (x,y,v_i)(x,y,vi)表示的连接关系容易发现可能有下面两种操作从y yy号矿井移步到x xx号矿井获得v i v_ivi的价值从x xx号矿井移步到y yy号矿井同样是获得v i v_ivi的价值。如此一来能得到下面两个相互交织的递推方程组{ f ( i , x ) f ( i − 1 , y ) v i f ( i , y ) f ( i − 1 , x ) v i \begin{cases} f(i,x) f(i-1,y) v_i \\ f(i,y) f(i-1,x) v_i \end{cases}{f(i,x)f(i−1,y)vif(i,y)f(i−1,x)vi最开始累计的价值为零因此初始条件是∀ t ∈ { 1 , 2 , ⋯ , n } , f ( 0 , t ) 0 \forall t \in \{1,2,\cdots, n\}, \quad f(0,t) 0∀t∈{1,2,⋯,n},f(0,t)0由于数据是2 × 10 5 2\times 10^52×105的数据规模因此O ( n 2 ) O(n^2)O(n2)的二维数组存所有的f ( i , j ) f(i,j)f(i,j)在空间复杂度上显然过不去需要考虑滚动优化将空间复杂度打到O ( n ) O(n)O(n)数组里只保留最近的最优即可。因为求最优解时只需要用最近一步迭代的结果继续往后推更早的用不到了。3. 代码usingSystem;classP15895{staticvoidMain(){inttConvert.ToInt32(Console.ReadLine());while(t--0){varnmConsole.ReadLine().Split();intnConvert.ToInt32(nm[0]);intmConvert.ToInt32(nm[1]);long[]fnewlong[n1];longresult0;for(inti0;im;i){varxyvConsole.ReadLine().Split();intxConvert.ToInt32(xyv[0]);intyConvert.ToInt32(xyv[1]);longvConvert.ToInt64(xyv[2]);longtmpxf[x],tmpyf[y];f[x]tmpyv;f[y]tmpxv;}for(inti1;in;i){if(f[i]result)resultf[i];}Console.WriteLine(result);}}}4. 轶事利用 C# 的托管等机制可以免去“多测不清空零分两行泪”以及内存泄漏的苦恼本题的模型其实是起源于东亚的一种梯子游戏 [1]。游戏结果完全仅由横线的排布决定无任何运气成分。换句话说出口和入口的对应关系其实就是一个已经定死的1 ∼ n 1\sim n1∼n的全排列。反映到这道题上选择一个入口后总共拿到多少奖励已经是板上钉钉的事。
