【欧拉路】Codeforces Round #508 (Div. 2) E. Maximum Matching_codeforces round 508 (div. 2)e

Step1 Problem:

给你 n 个块，每个块左右两边有颜色，中间是块的权值，如果不同的块的边颜色一样，那么它们可以合并成新的一块。
例：两个块分别是 c1 v1 c2, c2 v2 c1，那么这两个块可以变成 c1 v1+v2 c1，或者 c2 v1+v2 c2。
你可以选择 n 块的任意块，求合成后的权值最大值。
数据范围：
1<=n<=100, 1 <= c <= 4, 1 <= v <= 100000.

Step2 Ideas:

欧拉路径：如果图 G 中的一个路径包括每个边恰好一次，则该路径称为欧拉路径。
欧拉回路：如果一个回路是欧拉路径，则称为欧拉回路。
一个图奇点个数一定是偶数个
如果一个无向图是连通的，且最多只有两个奇点，则一定存在欧拉道路。

因为本题最多只有四个点，当连通块个数是 1 的时候 同时 四个点都是奇点，当前不是欧拉路。
否则都是欧拉路，如果是欧拉路代表能一笔走完，就代表可以把该连通块所有块都连一起，权值就是所有块的和。
核心点：如果不是欧拉路的话，代表不能一笔走完，我们就得去除某条边，对于当前图找最大权值的欧拉路。

Step3 Code:

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
struct node
{
    int to, w, rev, flag;//目的，权值，反向边，标记该边是否存在
};
int vis[10], d[10], c;
int bs[10];
vector<node> Map[5];
void dfs(int u)
{
    vis[u] = c;
    for(int i = 0; i < Map[u].size(); i++) {
        int to = Map[u][i].to, flag = Map[u][i].flag;
        if(flag == 1) continue;
        if(!vis[to]) dfs(to);
    }
}
int solve()
{
    c = 0;
    int cnt = 0, odd = 0;
    int ans = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= 4; i++) {
        if(!vis[i]) {
            c++;
            dfs(i), cnt++;
            int sum = 0;
            for(int j = 1; j <= 4; j++) {
                if(vis[j] == c) {
                    if(d[j]&1) odd++;
                    sum += bs[j];
                }
            }
            ans = max(ans, sum);
        }
    }
    if(cnt == 1 && odd == 4) return 0;//不是欧拉路
    else return ans;//该图存在欧拉路，返回权值最大的欧拉路
}
int main()
{
    int n, u, v, w;
    scanf("%d", &n);
    memset(d, 0, sizeof(d));//记录每个点的度
    memset(bs, 0, sizeof(bs));//记录到 v 的权值和
    for(int i = 1; i <= n; i++) {
        scanf("%d %d %d", &u, &w, &v);
        d[u]++, d[v]++;
        bs[v] += w;
        Map[u].push_back((node){v, w, Map[v].size(), 0});
        Map[v].push_back((node){u, w, Map[u].size()-1, 0});
    }
    int ans = 0;
    ans = solve();
    if(ans) {
        printf("%d\n", ans);
        return 0;
    }
    //删除边，找权值最大的欧拉路
    for(int i = 1; i <= 4; i++) {
        for(int j = 0; j < Map[i].size(); j++) {
            int to = Map[i][j].to, w = Map[i][j].w, &flag = Map[i][j].flag;
            if(to == i) continue;
            flag = 1;//删边
            Map[to][Map[i][j].rev].flag = 1;
            d[i]--, d[to]--;//减度
            ans = max(ans, solve()-w);//更新最大值
            Map[to][Map[i][j].rev].flag = 0;//恢复边
            flag = 0;
            d[i]++, d[to]++;
        }
    }
    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