E. Maximum Matching 欧拉回路 并查集

题意

有 n块砖头
每个砖头如下

一共有四种颜色,只有相同颜色可以相连接
问一条价值最大的砖块(连再一起的)

思路

把颜色看成端点
那么就是有n条路径
实际上就成了欧拉回路
因为只有四种颜只有
4个点度数都为奇数时
不可连成欧拉回路
那枚举每一条边 删除然后dfs
否则
就是联通块中价值最大的连通块
用并查集就可以了

AC代码

#include <bits/stdc++.h>
#define endl "\n" 
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
using namespace std;
typedef long long ll;
const  ll mod = 998244353;
const   double  PI = acos(-1.0);
const double EI = exp(1.0);
const int  N = 1e6 + 10;
const int M = 16;
const double  eps = 1e-8;
int n, val, c1[N], c2[N], v[N], deg[M], ban[N];
int fa[N], sum[M];
bool vis[N], mk[N];
int find(int x)
{
	if (fa[x] == x)
		return x;
	return fa[x] = find(fa[x]);
}
void join(int u, int v, int w)
{
	int x = find(u), y = find(v);
	if (x == y)
	{
		sum[x] += w;
		return;
	}
	fa[y] = x;
	sum[x] += (sum[y]+w);
	sum[y] = 0;
}
void dfs(int u)
{
	vis[u] = true;
	for (int j = 1; j <= n; j++)
	{
		if (ban[j] == true || mk[j]) continue;
		if (c1[j] != u && c2[j] != u)continue;
		mk[j] = true;
		val += v[j];
		dfs(c1[j] == u ? c2[j] : c1[j]);
	}
}
void solve()
{
	cin >> n;
	for (int i = 1; i < M; i++)fa[i] = i, sum[i] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> c1[i] >> v[i] >> c2[i];
		deg[c1[i]]++, deg[c2[i]]++;
		join(c1[i], c2[i], v[i]);
	}
	int nn = 4, res = 0;
	for (int i = 1; i <= nn; i++)
	{
		if (fa[i] != i) continue;
		int odd = 0;
		for (int j = 1; j <= nn; j++) if (find(i) == find(j) && deg[j] % 2 != 0) odd++;
		if (odd != 4)
		{
			res = max(res, sum[i]);
			continue;
		}
		for (int j = 1; j <= n; j++)
		{
			if (c1[j] == c2[j])  continue;
			memset(mk, 0, sizeof(mk));
			memset(vis, 0, sizeof(vis));
			ban[j] = true;
			for (int k = 1; k <= nn; k++)
			{
				if (k != c1[j] && k != c2[j])
				{
					val = 0;
					dfs(k);
					res = max(val, res);
					break;
				}
			}
			for (int k = 1; k <= nn; k++)
			{
				if (!vis[k])
				{
					val = 0;
					dfs(k);
					res = max(val, res);
				}
			}
			ban[j] = false;
		}
	}
	cout << res << endl;
}
int main()
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	//int t; cin >> t; while (t--)
	solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104