Maximum Matching
Contest: Codeforces Round 508 (Div. 2)
Difficulty rating: 2400
Tags: bitmasks, brute force, dfs and similar, dp, graphs

You are given $$$n$$$ blocks, each of them is of the form [color$$$_1$$$|value|color$$$_2$$$], where the block can also be flipped to get [color$$$_2$$$|value|color$$$_1$$$].

A sequence of blocks is called valid if the touching endpoints of neighboring blocks have the same color. For example, the sequence of three blocks A, B and C is valid if the left color of the B is the same as the right color of the A and the right color of the B is the same as the left color of C.

The value of the sequence is defined as the sum of the values of the blocks in this sequence.

Find the maximum possible value of the valid sequence that can be constructed from the subset of the given blocks. The blocks from the subset can be reordered and flipped if necessary. Each block can be used at most once in the sequence.

Input format:
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of given blocks.

Each of the following $$$n$$$ lines describes corresponding block and consists of $$$\mathrm{color}_{1,i}$$$, $$$\mathrm{value}_i$$$ and $$$\mathrm{color}_{2,i}$$$ ($$$1 \le \mathrm{color}_{1,i}, \mathrm{color}_{2,i} \le 4$$$, $$$1 \le \mathrm{value}_i \le 100\,000$$$).

Output format:
Print exactly one integer — the maximum total value of the subset of blocks, which makes a valid sequence.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, it is possible to form a valid sequence from all blocks.

One of the valid sequences is the following:

[4|2|1] [1|32|2] [2|8|3] [3|16|3] [3|4|4] [4|1|2]

The first block from the input ([2|1|4] $$$\to$$$ [4|1|2]) and second ([1|2|4] $$$\to$$$ [4|2|1]) are flipped.

In the second example, the optimal answers can be formed from the first three blocks as in the following (the second or the third block from the input is flipped):

[2|100000|1] [1|100000|1] [1|100000|2]

In the third example, it is not possible to form a valid sequence of two or more blocks, so the answer is a sequence consisting only of the first block since it is the block with the largest value.

Example input:
6
2 1 4
1 2 4
3 4 4
2 8 3
3 16 3
1 32 2

Example output:
63

Example input:
7
1 100000 1
1 100000 2
1 100000 2
4 50000 3
3 50000 4
4 50000 4
3 50000 3

Example output:
300000

Editorial:
Create a graph with $$$4$$$ nodes $$$1-4$$$ representing the colors. Then the value of a block serves as an edge between the two colors of that block.
Then the question reduces to finding an euler tour in the graph with the maximum sum of edges traveled. An euler tour may not exist with all the given edges, so the question is: Which edges do we remove?
One can note that there are $$$16$$$ types of edges. (Edges connecting 1 to 1, 1 to 2 and so on). There may be multiple edges of a specific type, however atmost 1 of it will be removed to form a valid euler tour. This is because if we have $$$2x + y$$$ edges between node $$$A$$$ and node $$$B$$$ where $$$0 \le y \le 1$$$, we can simply loop back and forth between $$$A$$$ and $$$B$$$ $$$x$$$ times to end up at the node we started from.
Since there are only $$$16$$$ types of edges, we can use bitmask to iterate over all the possibilities, and checking whether an euler tour exists in the graph with the marked edges removed (if there are multiple edges between node $$$A$$$ and node $$$B$$$, we remove only one edge, the one with the least value).
Refer to author's solution/any AC codes to see implementation details.
Overall Complexity: $$$O(2^{16} \times n)$$$
Bonus: Can you solve this question in $$$O(n^2)$$$? How about $$$O(n)$$$?