Codeforces 1038E 欧拉通路+并查集_codeforces 欧拉路+

题意： 给定$n$个形如$(a,w,b)$的块，其中$w$表示该块的值，$a$和$b$表示该块左部分和右部分的颜色，当且仅当两个块相连部分的颜色相同时，其可以组成一个更大的块，相应的值为两个小块之和。求$n$个块任意合法组合后可以得到的最大值。
题解： 可以把每块看成两点之间连了条权为$w$的边。
由于只有$4$种颜色，故有两种情况：
$1.$ 连通块有$1$个且有$4$个奇数点。
$2.$ 其他。
那么只有求出每个连通块的和即可。当处于第一种情况时，需要删一条边使得删掉该边后所有点都在，即删掉的边不能是桥，且因为求的是最大值故删掉的为非桥边值最小。
代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 5, M = 210;
int h[N], e[M], ne[M], w[M], idx = 2;
int g[N][N], n, res;
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int vis[M], d[N], temp;
void dfs(int u) {
	for(int &i = h[u]; i; i = ne[i]) {
		if(!vis[i >> 1]) {
			vis[i >> 1] = 1;
			temp += w[i];
			dfs(e[i]);
		}
	}
} 

int p[N];
int find(int x) {
	if(x != p[x]) p[x] = find(p[x]);
	return p[x];
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		int a, c, b; scanf("%d%d%d", &a, &c, &b);
		if(!p[a]) p[a] = a;
		if(!p[b]) p[b] = b;
		add(a, b, c), add(b, a, c);
		p[find(a)] = find(b);
		if(a != b) d[a]++, d[b]++;
	}

	int st[5] = {0}, cnt = 0;
	for(int i = 1; i <= 4; i++) if(h[i]) st[find(i)] = 1;
	for(int i = 1; i <= 4; i++) if(st[i]) cnt++;
	if(cnt == 1) {
		int odd = 0;
		for(int i = 1; i <= 4; i++)
			if(d[i] & 1) odd++;
		
		int tres = 0;
		for(int i = 2; i < idx; i += 2) tres += w[i];
		if(odd == 4) {
			int Mi = 1e9;
			for(int u = 1; u <= 4; u++)
				for(int i = h[u]; i; i = ne[i]) { 
					if(u == e[i] || d[u] == 1 || d[e[i]] == 1) continue;
					Mi = min(Mi, w[i]);
				} 
			tres -= Mi;
		}
		res = tres;
	}
	else {
		for(int i = 1; i <= 4; i++)
			if(h[i]) {
				temp = 0;
				dfs(i);
				res = max(res, temp);
			}
	}
	printf("%d\n", res);
	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