1038E - Maximum Matching - CodeForces Solution

import sys
input = sys.stdin.buffer.readline

def find_root(root_dict, x):
    L = []
    while x != root_dict[x]:
        L.append(x)
        x = root_dict[x]
    for y in L:
        root_dict[y] = x 
    return x

def calculate_stuff(edge_list):
    single = [0 for i in range(5)]
    root_dict = [i for i in range(5)]
    g = [[] for i in range(5)]
    for c1, v, c2 in edge_list:
        if c1==c2:
            single[c1]+=v
        else:
            g[c1].append([c2, v])
            g[c2].append([c1, v])
            i1 = find_root(root_dict, c1)
            i2 = find_root(root_dict, c2)
            root_dict[i1] = i2
    roots = [[] for i in range(5)]
    for i in range(1, 5):
        i1 = find_root(root_dict, i)
        roots[i1].append(i)
    return single, g, roots
    
def process(A):
    n = len(A)
    single, g, roots = calculate_stuff(A)
    answer = 0
    has_four = False
    for i in range(1, 5):
        if len(roots[i]) > 1:
            component = roots[i]
            entry = 0
            edges = []
            count = 0
            for i1 in component:
                entry+=single[i1]
                count+=(len(g[i1]) % 2)
                for i2, v in g[i1]:
                    if i1 < i2:
                        edges.append(v)
            if count==0 or count==2:
                entry+=sum(edges)
                answer = max(answer, entry)
            else:
                assert count==4
                has_four = True
        else:
            answer = max(answer, single[i])
    if has_four:
        for I in range(n):
            if A[I][0] != A[I][2]:
                A2 = [A[i] for i in range(n) if i != I]
                single2, g2, roots2 = calculate_stuff(A2)
                answer2 = max(single2)
                for i in range(1, 5):
                    if len(roots2[i]) > 1:
                        component = roots2[i]
                        entry = 0
                        edges = []
                        count = 0
                        for i1 in component:
                            entry+=single2[i1]
                            count+=(len(g2[i1]) % 2)
                            for i2, v in g2[i1]:
                                if i1 < i2:
                                    edges.append(v)
                                                entry+=sum(edges)
                        answer2 = max(answer, entry)
                    else:
                        answer2 = max(answer2, single2[i])
                answer = max(answer, answer2)
    print(answer)
        
    
n = int(input())
A = []
for i in range(n):
    c1, v, c2 = [int(x) for x in input().split()]
    A.append([c1, v, c2])
process(A)