当前位置:   article > 正文

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

maximum matching codeforces - 1038e

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

8.1 题意

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

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

8.2 解题过程

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

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

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

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

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

时间复杂度: O ( n 2 ) O(n^2) O(n2)

8.3 错误点

真的很嫌弃自己,写个这么简单的程序能写出一堆 bug \texttt{bug} 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/1015942
推荐阅读
相关标签
  

闽ICP备14008679号