Codeforces1038 E. Maximum Matching（欧拉路）_codeforces 欧拉路

题意：

有n个砖块，每个砖块形如[color1|value|color2]，砖块左右两边是颜色，中间是砖块的值
两个砖块A、B能够连接成AB的条件是A的右边颜色与B的左边相同
允许将砖块翻转

现在要你从这n个砖块挑出若干砖块，要求能够连在一起，问最大权值和是多少

数据范围：n<=100，1<=颜色数<=4

解法：

抽象成图论模型：
将颜色看作点，那么每个砖块都是两点之间的一条边（砖块两边颜色相同时就是自环）
因为最多4种颜色，那么就会形成4个点n条边的图（颜色数可能小于4，但是方便起见直接当作4个点，允许存在无边的空点）

那么问题就变为选择出图中若干条边，满足其能构成欧拉路的最大权值和
欧拉路前提：图连通
欧拉路条件：
1.所有点的度数都是偶数(即无向图欧拉图)，这种情况下任意点可作为起点和终点，此时是欧拉回路
2.只有两个点的度数是奇数，其他点的度数是偶数，这种情况下度数为奇数的两个点分别为起点和终点

如果图中有多个连通块，计算每个连通块中欧拉路的权值，取max就是答案
对连通块内节点数量的不同进行分类讨论：
1.如果连通块内有一个点，那么只有自环，一定能构成欧拉路
2.如果连通块内有两个点，因为每条边贡献两个度，所以总度数一定是偶数，则这个连通块的度数分配可能为（两偶）或者（两奇），一定能构成欧拉路
3.如果连通块内有三个点，因为每条边贡献两个度，所以总度数一定是偶数，则这个连通块的度数分配可能为（两奇一偶）或（三个偶），一定能构成欧拉路
4.如果连通块内有四个点，因为每条边贡献两个度，所以总度数一定是偶数，则这个连通块的度数分配可能为（四偶）或（两奇两偶）或（四奇）。只有当（四奇）的情况不能构成欧拉路，这时候删掉一条边，就能变成（两奇两偶），因为最多只有100条边，枚举删除连通块内的边，计算欧拉路权值取max即可。但是删边之后可能将当前连通块分为（两偶+两奇）的连通块，这时候分别对两个连通块分别计算一遍取max，注意删除的边不能是自环，因为删除自环不影响奇偶性。

可以用带权并查集维护连通块内的节点数和边权和，这样的话对于可以直接构成欧拉路的连通块就可以直接得到边权和了。

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=105;
struct E{
    int v,w,id;
};
vector<E>g[5];
int d[5];
int ans;
int n;
//
int mark[maxm];//边访问标记
int tempsum;
//
int pre[5];
int sum[5];
int cnt[5];
int ffind(int x){
    return pre[x]==x?x:pre[x]=ffind(pre[x]);
}
void dfs(int x){
    for(auto t:g[x]){
        if(mark[t.id])continue;
        mark[t.id]=1;
        tempsum+=t.w;
        dfs(t.v);
    }
}
bool check(int st,int ed,int del){//bfs判断删边之后st能否到达ed
    int vis[5]={0};
    queue<int>q;
    q.push(st);
    vis[st]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(auto t:g[x]){
            if(t.id==del)continue;
            if(vis[t.v])continue;
            vis[t.v]=1;
            q.push(t.v);
        }
    }
    return vis[ed];
}
signed main(){
    for(int i=1;i<=4;i++){
        pre[i]=i;
        cnt[i]=1;
        sum[i]=0;
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,c,b;cin>>a>>c>>b;
        g[a].push_back({b,c,i});
        g[b].push_back({a,c,i});
        //统计度数
        d[a]++,d[b]++;
        //维护连通块
        int x=ffind(a);
        int y=ffind(b);
        if(x==y){
            sum[x]+=c;//连通块总权值
        }else{
            pre[x]=y;//合并连通块
            sum[y]+=sum[x]+c;//连通块总权值
            cnt[y]+=cnt[x];//连通块节点数
        }
    }
    for(int i=1;i<=4;i++){
        if(pre[i]==i){
            if(cnt[i]<=3){//点数<=3能直接构成欧拉路
                ans=max(ans,sum[i]);
            }else{//cnt[i]==4,可能不能构成欧拉路
                int odd=0;
                for(int j=1;j<=4;j++){
                    if(d[j]%2){
                        odd++;
                    }
                }
                if(odd==0||odd==2){//可以构成欧拉路
                    ans=max(ans,sum[i]);
                }else{//否则枚举删除连通块内的边
                    int root=i;
                    for(int k=1;k<=4;k++){
                        if(ffind(k)!=root)continue;
                        for(auto t:g[k]){
                            int a=k,b=t.v;
                            if(a==b)continue;//跳过自环
                            int link=check(a,b,t.id);//判断删除之后是否分为两个连通块
                            if(link){//仍在一个连通块则直接计算权值和
                                ans=max(ans,sum[root]-t.w);
                            }else{//否则分别对两个连通块计算答案
                                //
                                for(int e=1;e<=n;e++){
                                    mark[e]=0;
                                }
                                mark[t.id]=1;
                                tempsum=0;
                                dfs(a);
                                ans=max(ans,tempsum);
                                //
                                for(int e=1;e<=n;e++){
                                    mark[e]=0;
                                }
                                mark[t.id]=1;
                                tempsum=0;
                                dfs(b);
                                ans=max(ans,tempsum);
                                //
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
    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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120