← 返回题目列表

Codeforces · 1038/E

E. 最大匹配

中文机器翻译题面 查看原题

你有$$$n$$$块,每个块的形式为[color$$$_1$$$|value|color$$$_2$$$],其中块也可以翻转得到[color$$$_2$$$|value|color$$$_1$$$]。

如果相邻块的接触端点具有相同的颜色,则块序列被称为有效。例如,如果 B 的左侧颜色与 A 的右侧颜色相同,并且 B 的右侧颜色与 C 的左侧颜色相同,则三个块 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{颜色}_{2,i} \le 4$$$, $$$1 \le \mathrm{值}_i \le 100\,000$$$)。

输出

精确打印一个整数——块子集的最大总值,这构成了一个有效的序列。

示例

输入 #1

6
2 1 4
1 2 4
3 4 4
2 8 3
3 16 3
1 32 2

输出 #1

63

输入 #2

7
1 100000 1
1 100000 2
1 100000 2
4 50000 3
3 50000 4
4 50000 4
3 50000 3

输出 #2

300000

输入 #3

4
1 1000 1
2 500 2
3 250 3
4 125 4

输出 #3

1000

注意

在第一个示例中,可以从所有块形成有效序列。

有效序列之一如下:

[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]

在第三个示例中,不可能形成两个或多个块的有效序列,因此答案是仅由第一个块组成的序列,因为它是具有最大值的块。