CF1038E Maximum Matching

给定 $n$ 个方块，每个方块的格式为 $color_1\mid value \mid color_2$，方块也可以翻转得到 $color_2 \mid value \mid color_1$。 如果一个方块序列中相邻方块的接触端颜色相同，则称该序列为有效序列。例如，由三个方块 A、B 和 C 组成的序列是有效的，当且仅当 B 的左侧颜色与 A 的右侧颜色相同，且 B 的右侧颜色与 C 的左侧颜色相同。 序列的值定义为该序列中所有方块的值之和。 请从给定的方块子集中构造一个有效序列，并找到该序列的最大可能值。子集中的方块可以重新排序和翻转。每个方块在序列中最多只能使用一次。

输入的第一行包含一个整数 $n$（$1 \le n \le 100$）—— 给定方块的数量。 接下来的 $n$ 行描述每个方块，每行包含 $\mathrm{color}_{1,i}$、$\mathrm{value}_i$ 和 $\mathrm{color}_{2,i}$（$1 \le \mathrm{color}_{1,i}, \mathrm{color}_{2,i} \le 4$，$1 \le \mathrm{value}_i \le 100\,000$）。

输出一个整数 —— 能够构成有效序列的方块子集的最大总值。

第一个样例中，可以使用所有方块构造有效序列。 一种有效序列如下： $4|2|1$，$1|32|2$，$2|8|3$，$3|16|3$，$3|4|4$，$4|1|2$ 输入的第一个方块（$2|1|4$ $\to$ $4|1|2$）和第二个方块（$1|2|4$ $\to$ $4|2|1$）被翻转。 第二个样例中，最优解可由前三个方块构造（输入的第二个或第三个方块被翻转）： $2|100000|1$，$1|100000|1$，$1|100000|2$ 第三个样例中，无法构造包含两个或更多方块的有效序列，因此答案是仅包含第一个方块的序列（因为它是数值最大的方块）。 翻译由 DeepSeek V3+R1 完成