Codeforces - 1038E - Maximum Matching（欧拉回路 + 建图）_maximum matching codeforces - 1038e

题目链接：https://codeforces.com/contest/1038/problem/E

8.1 题意

有 $n(1\le n\le 100)$ 个条带，每个条带的格式为 $\text{[color1|value|color2]}$($1\le \text{color}\le 4,1\le \text{value}\le 10^5$)，两个条带可以连接当且仅当它们有一个公共端。

问权值之和最大的连通条带。

8.2 解题过程

建立一个 $4$ 个结点的图，对于每一个条带来说，颜色向颜色建边。

则我们会发现，欧拉通路不存在的情况只有一种：只有一个连通块，且奇度顶点的个数为 $4$。

其他情况下，答案就是每个连通块权值（等价于欧拉通路的权值和）的最大值。

在欧拉通路不存在时，只需删掉任意一条非自环的边，即可回到上面的合法情况。

因此，在欧拉通路不存在时，枚举要删的边，然后按照合法情况进行求解，最后取最大答案即可。

时间复杂度：$O(n^2)$。

8.3 错误点

真的很嫌弃自己，写个这么简单的程序能写出一堆 $\text{bug}$ 来，还 WA 了好多发。

1. 枚举要删的边时，一定要跳过自环，因为自环删掉之后奇度顶点数量不变。
2. 删边时不要忘记更新两个顶点的度。

8.4 代码

int n, m;
int head[maxn], cnt;
int col[maxn], deg[maxn], cntt[maxn], sum[maxn];
bool mark[2 * maxn];
struct edge
{
    int v, nxt, w;
} Edge[2 * maxn];
void init()
{
    memset(head, -1, sizeof(head));
    cnt = 0;
}
void reset() {
    memset(col, 0, sizeof(col));
    memset(sum, 0, sizeof(sum));
    memset(cntt, 0, sizeof(cntt));
}
void addedge(int u, int v, int w)
{
    Edge[cnt].v = v;
    Edge[cnt].w = w;
    Edge[cnt].nxt = head[u];
    head[u] = cnt++;
}
void dfs(int id, int color) {
    col[id] = color;
    for (int i = head[id]; i != -1; i = Edge[i].nxt) {
        int v = Edge[i].v;
        if (!col[v] && !mark[i]) dfs(v, color);
    }
}
int solve() {
    reset();
    int num = 0;
    for (int i = 1; i <= 4; i++) {
        if (!col[i]) dfs(i, ++num);
    }
    for (int i = 1; i <= 4; i++) {
        if (deg[i] & 1) cntt[col[i]]++;
    }
    for (int i = 0; i < cnt; i += 2) {
        if (mark[i]) continue;
        int u = Edge[i ^ 1].v;
        int v = Edge[i].v;
        int w = Edge[i].w;
        sum[col[u]] += w;
    }
    int res = 0;
    for (int i = 1; i <= num; i++) {
        res = max(res, sum[i]);
    }
    return res;
}
int main()
{
    scanf("%d", &n);
    init();
    for (int i = 1; i <= n; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &w, &v);
        addedge(u, v, w);
        addedge(v, u, w);
        deg[u]++, deg[v]++;
    }
    int ans = solve();
    bool isok = true;
    for (int i = 1; i <= 4; i++) {
        if (cntt[i] > 2) {
            isok = false;
            break;
        }
    }
    if (isok) return 0 * printf("%d\n", ans);
    ans = 0;
    for (int i = 0; i < cnt; i += 2) {
        int u = Edge[i ^ 1].v;
        int v = Edge[i].v;
        if (u == v) continue;
        deg[u]--, deg[v]--;
        mark[i] = mark[i ^ 1] = true;
        ans = max(ans, solve());
        mark[i] = mark[i ^ 1] = false;
        deg[u]++, deg[v]++;
    }
    printf("%d\n", ans);
    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