[CSP-S 2022] 假期计划 P8817
小熊的地图上有 n n n 1 1 1 2 , 3 , … , n 2, 3, \ldots, n 2 , 3 , … , n x x x z 1 z_1 z 1 z 1 z_1 z 1 z 2 z_2 z 2 z k − 1 z_{k - 1} z k − 1 z k z_k z k z k z_k z k y y y x x x y y y k k k x x x y y y 0 0 0
很快就要放假了，小熊计划从家出发去 4 4 4 不同 的景点游玩，完成 5 5 5 → \to → → \to → → \to → → \to → → \to → k k k → \to → → \to →
假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同 景点的分数之 和最大。
输入数据格式
第一行包含三个正整数 n , m , k n, m, k n , m , k
第二行包含 n − 1 n - 1 n − 1 2 , 3 , … , n 2, 3, \ldots, n 2 , 3 , … , n
接下来 m m m x , y x, y x , y x x x y y y 1 ≤ x , y ≤ n 1 \le x, y \le n 1 ≤ x , y ≤ n
输出数据格式
输出一个正整数，表示小熊经过的 4 4 4
输入输出样例
输入 #1Copy 输出 #1 8 8 1 27 输入 #2Copy 输出 #2 --- --- 7 9 0 7
说明与提示
【样例解释 #1】
当计划的行程为 1 → 2 → 3 → 5 → 7 → 1 1 \to 2 \to 3 \to 5 \to 7 \to 1 1 → 2 → 3 → 5 → 7 → 1 4 4 4 9 + 7 + 8 + 3 = 27 9 + 7 + 8 + 3 = 27 9 + 7 + 8 + 3 = 27
行程 1 → 3 → 5 → 7 → 8 → 1 1 \to 3 \to 5 \to 7 \to 8 \to 1 1 → 3 → 5 → 7 → 8 → 1 24 24 24 1 → 3 → 2 → 8 → 7 → 1 1 \to 3 \to 2 \to 8 \to 7 \to 1 1 → 3 → 2 → 8 → 7 → 1 25 25 25
行程 1 → 2 → 3 → 5 → 8 → 1 1 \to 2 \to 3 \to 5 \to 8 \to 1 1 → 2 → 3 → 5 → 8 → 1 30 30 30 5 → 8 5 \to 8 5 → 8 2 2 2 k = 1 k = 1 k = 1
行程 1 → 2 → 3 → 2 → 3 → 1 1 \to 2 \to 3 \to 2 \to 3 \to 1 1 → 2 → 3 → 2 → 3 → 1 32 32 32 4 4 4
【样例 #3】
见附件中的 holiday/holiday3.in 与 holiday/holiday3.ans。
【数据范围】
对于所有数据，保证 5 ≤ n ≤ 2500 5 \le n \le 2500 5 ≤ n ≤ 2500 1 ≤ m ≤ 10000 1 \le m \le 10000 1 ≤ m ≤ 10000 0 ≤ k ≤ 100 0 \le k \le 100 0 ≤ k ≤ 100 1 ≤ s i ≤ 10 18 1 \le s_i \le {10}^{18} 1 ≤ s i ≤ 10 18
测试点编号 n ≤ n \le n ≤ m ≤ m \le m ≤ k ≤ k \le k ≤ 1 ∼ 3 1 \sim 3 1 ∼ 3 10 10 10 20 20 20 0 0 0 4 ∼ 5 4 \sim 5 4 ∼ 5 10 10 10 20 20 20 5 5 5 6 ∼ 8 6 \sim 8 6 ∼ 8 20 20 20 50 50 50 100 100 100 9 ∼ 11 9 \sim 11 9 ∼ 11 300 300 300 1000 1000 1000 0 0 0 12 ∼ 14 12 \sim 14 12 ∼ 14 300 300 300 1000 1000 1000 100 100 100 15 ∼ 17 15 \sim 17 15 ∼ 17 2500 2500 2500 10000 10000 10000 0 0 0 18 ∼ 20 18 \sim 20 18 ∼ 20 2500 2500 2500 10000 10000 10000 100 100 100
holiday.zip
*练习笔记 暂无人完成练习，做第一个完成练习的人—-first blood ！ 我要练习