题解：CF405E Graph Cutting

Suin_tryin · 2026-10-22 13:52:36 · 题解

CF405E Graph Cutting（青，*2300）

首先 m 为奇数一定无解。下面给出 m 为偶数的构造。

考虑图是一棵树。由于叶子的度数是 1，所以从下往上匹配。对于一个 u 子树，期望子树内的边尽可能全部匹配，如果子树内有奇数条边，由于从下往上匹配，没匹配的一定是一个连着 u 和儿子 v 的边，让 u 和 u 父亲的边和它匹配即可。

具体的，对于每个节点，标记子树内未匹配边端点 t。匹配 u 子树时，对于有标记的儿子，让 (u,v) 和 (v,t_v) 匹配，对于没有标记的儿子 v，(u,v) 两两匹配，匹配不上就标记 t_u \leftarrow v。这样每条边一定能够找到匹配。

对于无向图，考虑像树一样做。建出 dfs 生成树，唯一问题在于非树边。把每条非树边看作连接的是空子树，搜索时只走树边，匹配按照上文思路即可。

code