Description：

每个牌两端有颜色，中间有权值，求一个权值和最大的接龙。

$1\leqslant n\leqslant 100,1\leqslant color\leqslant 4$

Solution：

不难想到欧拉回路相关，既然只有 $4$ 个点，那就只有在四个点度数都是奇数的时候才不行，于是发现最多只会删掉一条边，就可以枚举删掉那条边，剩下的部分可能会分成许多联通快，这些联通块都是有欧拉回路的，于是可以直接用并查集统计每个联通块内边的权值和取最大更新答案即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 110

struct block

{

	int u,v,w;

	bool tag;

}s[MAXN];

int ind[5];

int f[5];

long long g[5];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

bool v[5];

long long calc()

{

	long long res = 0;

	f[1] = 1;f[2] = 2;f[3] = 3;f[4] = 4;

	memset(g,0,sizeof(g));

	for(int i = 1;i <= n;++i)

	{

		if(!s[i].tag)continue;

		int p = find(s[i].u),q = find(s[i].v);

		if(p == q)g[p] += s[i].w;

		else

		{

			f[p] = q;

			g[q] += g[p] + s[i].w;

		}

	}

	memset(v,false,sizeof(v));

	for(int i = 1;i <= 4;++i)

	{

		if(!v[find(i)])

		{

			res = max(res,g[find(i)]);

			v[find(i)] = true;

		}

	}

	return res;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d%d",&s[i].u,&s[i].w,&s[i].v);

		s[i].tag = true;

		++ind[s[i].u];++ind[s[i].v];

	}

	int cnt = (ind[1] % 2) + (ind[2] % 2) + (ind[3] % 2) + (ind[4] % 2);

	long long ans = 0;

	if(cnt == 0 || cnt == 2)ans = calc();

	for(int i = 1;i <= n;++i)

	{

		s[i].tag = false;

		--ind[s[i].u];--ind[s[i].v];

		int cnt = (ind[1] % 2) + (ind[2] % 2) + (ind[3] % 2) + (ind[4] % 2);

		if(cnt == 0 || cnt == 2)ans = max(ans,calc());

		++ind[s[i].u];++ind[s[i].v];

		s[i].tag = true;

	}

	cout << ans << endl;

	return 0;

}