[CF1038E]Maximum Matching_cf1032f vasya and maximum matching

题目

传送门 to CF

传送门 to luogu

传送门 to VJ

思路

图论模型

一个合法序列的最后一个方块，只由倒数第二个方块所限制。

这样的限制，往往可以建立图论模型。

注意到一个方块的本质是让结尾颜色变化一次。将一个方块两边的颜色 $⟨a,b⟩$ 视作一条连接 $a,b$ 的双向边。则答案为原图中边不相交的最长路径。

挑战 $\mathtt{N}\mathtt{P}-\mathtt{H}\mathtt{a}\mathtt{r}\mathtt{d}$

边不相交？这似乎是 欧拉路径 的必要条件呢！

如果我把走过的边抽象出来，这一定是一条欧拉路径（小知识：其充要条件是奇点数量不超过二）。

于是，我们力求找到原图的边集的子集 $E^{\prime }(E^{\prime }\subseteq E)$ ，满足 $G^{\prime }=(V,E^{\prime })$ 存在欧拉路径。

这难吗？不难。如果 $⟨a,b⟩$ 之间有两条边不属于 $E^{\prime }$ ，则将这两条边加入，仍然存在欧拉路径（因为 $a,b$ 的度数的奇偶性都没有变化）。

那么，我们知道了这一点： $⟨a,b⟩$ 之间最多只有一条边没有被经过（或者是全部都没有被经过）。

所以大力枚举吧！用 $2^6$ 来枚举，哪几种边是没有被全部经过的。之所以指数是六，是因为 这是我算出来的 删掉的边不会是自环，于是只有六种不同的边。

然后检测，并计算答案。战斗就结束了。有意思的是， $\mathcal{O}(n)$ 只来自于读入！

——言外之意：我允许 $n$ 达到 $10^6$ 级别。

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0' or c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c and c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int x){
	if(x > 9) writeint(x/10);
	putchar((x%10)^48);
}
# define MB template < class T >
MB void getMax(T &a,const T &b){ if(a < b) a = b; }
MB void getMin(T &a,const T &b){ if(b < a) a = b; }

const int MaxN = 105, infty = (1<<28)-1;
int sum[4][4], minV[4][4], cnt[4][4];

# define FOR(o) for(int o=0; o<4; ++o)

void input(){
	int n = readint();
	FOR(i) FOR(j) minV[i][j] = infty;
	for(int i=1,l,v,r; i<=n; ++i){
		l = readint()-1;
		v = readint(); // 颜色设置为[0,4)
		r = readint()-1;
		if(l > r) swap(l,r); // 小->大
		sum[l][r] += v, ++ cnt[l][r];
		getMin(minV[l][r],v);
	}
	FOR(i) for(int j=0; j<i; ++j){
		sum[i][j] = sum[j][i];
		minV[i][j] = minV[j][i];
		cnt[i][j] = cnt[j][i];
	} // 大->小
}

bool vis[4], deg[4]; int odd;
int dfs(int x){ // 返回答案的两倍（一条边会被加两次）
	if(vis[x] == true) return 0;
	vis[x] = true; int res = sum[x][x];
	FOR(i) if(x != i and cnt[x][i] > 0){
		res += sum[x][i]+dfs(i);
		if(cnt[x][i]%2 == 1)
			deg[x] = not deg[x];
	}
	if(deg[x]) ++ odd; return res+sum[x][x];
}

int HASH(int l,int r){
	return r+l-(l==0);
} // 请自行验证，顺序为(0,1)(0,2)(0,3)(1,2)(1,3)(2,3)
void solve(){
	int ans = 0;
	for(int S=(1<<6)-1; ~S; --S){
		bool ok = true;
		FOR(i) for(int j=i+1; j<4; ++j)
			if(cnt[i][j] == 0 and (S>>HASH(i,j)&1)){
				ok = false; break;
			} // 删掉了不存在的边 
		if(not ok) continue;
		FOR(i) vis[i] = deg[i] = false;

		FOR(i) for(int j=i+1; j<4; ++j)
			if((S>>HASH(i,j)&1) != 0){
				-- cnt[i][j], -- cnt[j][i];
				sum[i][j] -= minV[i][j];
				sum[j][i] -= minV[j][i];
			} // 对图进行删边操作

		FOR(i) if(not vis[i]){
			odd = 0; int d = dfs(i)>>1;
			if(odd < 3) getMax(ans,d);
		}
		
		FOR(i) for(int j=i+1; j<4; ++j)
			if((S>>HASH(i,j)&1) != 0){
				++ cnt[i][j], ++ cnt[j][i];
				sum[i][j] += minV[i][j];
				sum[j][i] += minV[j][i];
			}/* 将图还原 */
	}
	printf("%d\n",ans);
}

int main(){
	input(), solve();
	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