BZOJ3706 反色刷

问题引入

想象你面对一个复杂的线路图，每条边要么是黑色，要么是白色。你被赋予了一种神奇的能力：可以选择任意一条回路，沿着它走一遍，途中经过的所有边都会“反色”——黑变白，白变黑。

现在的问题是：能否通过若干次这样的操作，让图中所有的边都变成白色？如果能，最少需要多少次操作？

关键结论

思考（~~看标签~~）后，可以发现这个问题跟欧拉回路有关系。

可行性条件

只有连通块中黑边数为偶数时，这个连通图能通过回路反色操作将所有边变白。

原因：每次操作要改变偶数条边的颜色（因为回路闭合，进去和离开顶点的次数相同）。所以，黑边数的奇偶性在操作过程中不变。如果原来黑边数为奇数，无论怎么干，总会剩至少一条黑边。

无解条件

要是连通块中度数为奇数的顶点个数不是

0

，那这个询问就无解了（此时输出

-1

）。

原因：操作的本质就是沿着欧拉回路进行的。根据欧拉图理论，一个图要是有欧拉回路，它的所有顶点度数必须为偶数。如果有奇点，就找不到经过所有边的闭合路径，某些边就可能永远无法被操作。

最少操作次数

对于有解的连通块，最少操作次数就等于这个连通块的黑边数除以

2

。

原因：每次操作能处理

2

条黑边，所以黑边数除以

2

就是最小操作次数。

实现

数据结构

我们用并查集来维护图的连通性，同时实时跟踪每个连通块的关键信息：

CPP

int blk[MAXN];    // 每个连通块的黑边数
int odd[MAXN];    // 每个连通块的奇点数
int bcnt;         // 包含黑边的连通块数
int ocnt;         // 包含奇点的连通块数

更新逻辑

当边的颜色变化时，要：

更新连通块的黑边数
调整相关顶点的度数
重新计算奇点数
维护全局统计的信息

这个过程可以在极短的时间内完成。

查询处理

如果存在奇点，直接返回 $-1$ （无解）
否则，返回包含黑边的连通块数（bcnt）

警告：是连通块数，不是黑边数。

算法性能

时间复杂度： $O((m+q)\alpha(n))$ （ $\alpha(n)$ 是反阿克曼函数）
空间复杂度： $O(n)$

代码

CPP

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e6 + 8;
int n, m, q, deg[MAXN], dsu[MAXN], bcnt, blk[MAXN], ocnt, odd[MAXN];  // 连通块内黑边数和奇点数
struct Edge {
	int u, v, w;
} edges[MAXN];
int find(int u) { return dsu[u] == u ? u : dsu[u] = find(dsu[u]); }
void unite(int u, int v) {
	int fu = find(u), fv = find(v);
	if (fu == fv) return;
	if (blk[fu] && blk[fv]) bcnt--;
	if (odd[fu] && odd[fv]) ocnt--;
	dsu[fu] = fv, blk[fv] += blk[fu], odd[fv] += odd[fu];
}
void upd_blk_edge(int u, int v, int w) {
	int root = find(u);
	if (find(v) != root) return;
	bcnt -= (blk[root] > 0);
	blk[root] += w;  // 更新连通块内黑边数
	bcnt += (blk[root] > 0);
	ocnt -= (odd[root] > 0);
	odd[root] -= (deg[u] & 1), odd[root] -= (deg[v] & 1);
	deg[u]++, deg[v]++;
	odd[root] += (deg[u] & 1), odd[root] += (deg[v] & 1);
	ocnt += (odd[root] > 0);
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) dsu[i] = i;
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w, edges[i] = {u, v, w};
		unite(u, v);
		if (w) upd_blk_edge(u, v, w);
	}
	cin >> q;
	while (q--) {
		int op, x;
		cin >> op;
		if (op == 1) {
			cin >> x;
			auto [u, v, w] = edges[x];
			w ? upd_blk_edge(u, v, -1) : upd_blk_edge(u, v, 1);
			edges[x].w = !w;
		}
		if (op == 2) cout << (ocnt ? -1 : bcnt) << "\n";
	}
	return 0;
}

题解：P10777 BZOJ3706 反色刷

文章操作