题解

问题重述

给定一个 $n \times n$ 二分图（左右各 $n$ 个点），边有黑色（$c=1$）或白色（$c=0$）。求一个完美匹配，使得其中黑色边的数量为偶数。如果存在多个解，输出任意一个；如果无解，输出 -1。

---

核心难点

这是一个带约束的完美匹配问题：
不仅要找完美匹配，还要满足匹配中黑色边数 $\bmod\ 2 = 0$。

如果去掉颜色约束，就是经典的二分图完美匹配问题（可用匈牙利算法或最大流解决）。
但现在多了奇偶性要求，不能直接套用传统算法。

---

关键思路：奇偶性作为线性约束

设 $x_e \in \{0,1\}$ 表示边 $e$ 是否在匹配中。完美匹配的条件等价于：

1. $\forall$ 左部点 $u$：$\sum_{e \in \delta(u)} x_e = 1$
2. $\forall$ 右部点 $v$：$\sum_{e \in \delta(v)} x_e = 1$

其中 $\delta(u)$ 表示与 $u$ 关联的边集。

黑色边数偶数条件：
设 $w_e = c_e$（黑色为1，白色为0），则要求：

$$\sum_{e} w_e x_e \equiv 0 \pmod 2$$

---

解决框架：模 2 线性方程组

上述条件在 $\mathbb{F}_2$（模2域）下可写成线性方程组：

• 对于每个点 $p$：$\sum_{e \in \delta(p)} x_e \equiv 1 \pmod 2$（因为每个点恰好匹配一条边，模2下等于1）。
• 颜色约束：$\sum_{e} w_e x_e \equiv 0 \pmod 2$。

这是一个有 $2n+1$ 个方程（每个点一个方程 + 一个颜色奇偶方程）、$m$ 个变量的模2线性方程组。
我们需要找出 $\{0,1\}$ 解，且解对应一个匹配（在整数意义上每个点度数为1，不仅仅模2）。

---

分析解的存在性

在 $\mathbb{F}_2$ 中，点度方程是相关的：所有左部点方程之和 = 所有右部点方程之和（都等于 $\sum_e 2x_e \equiv 0$）。
因此独立方程最多 $2n$ 个，加上颜色约束共 $2n+1$ 个，但可能秩不足 $2n+1$。

关键观察：
如果我们先忽略颜色约束，找到任意一个完美匹配 $M_0$。设 $M_0$ 中黑色边数为 $s_0 \bmod 2$。

• 若 $s_0 \equiv 0 \pmod 2$，则 $M_0$ 就是解。
• 若 $s_0 \equiv 1 \pmod 2$，我们需要调整匹配，改变黑色边数的奇偶性。

---

如何改变奇偶性

考虑对称差操作：如果 $M_0 \oplus C$ 仍然是完美匹配，且 $C$ 是一个偶环（在二分图中是偶长度环），那么 $M_0$ 与 $C$ 的对称差会翻转 $C$ 中每条边的选中状态。

设 $M_0$ 中黑色边数 $s_0$，$C$ 中属于 $M_0$ 的黑色边数为 $a$，不在 $M_0$ 中的黑色边数为 $b$。
对称差后黑色边数变化：原来 $a$ 条被去掉，原来 $b$ 条被加入，净变化 $b-a$。

我们希望 $s_0 + (b-a)$ 为偶数，即 $b-a$ 与 $s_0$ 同奇偶性。
特别地，如果能找到环 $C$ 使得 $b-a \equiv 1 \pmod 2$，则对称差后奇偶性翻转。

---

构造性算法思路

1. 找到任意完美匹配 $M_0$（用匈牙利算法或最大流）。

2. 计算 $M_0$ 中黑色边数 $s_0$。

3. 如果 $s_0$ 为偶数，输出 $M_0$。

4. 如果 $s_0$ 为奇数，尝试找一个偶环 $C$ 使得与 $M_0$ 对称差后黑色边奇偶性翻转。

   • 将 $M_0$ 的边看作从左到右的匹配边，其余边从右到左。
   • 在这样得到的有向图中，找环相当于在残量图中搜索。
   • 需要环中黑色边数（考虑方向）的奇偶性满足条件。

5. 如果找不到这样的环，则无解。

---

更系统的处理：图论建模

构造一个新图 $G'$：

• 点集不变。
• 对每条原图的边 $e = (u,v)$，如果 $e \in M_0$，则加有向边 $v \to u$（容量为反向）；否则加有向边 $u \to v$（容量为正向）。
• 给黑色边赋权1，白色边赋权0。

在 $G'$ 中找一个有向环，使得环上边的权值和为奇数（模2意义下）。
这是因为环的权值奇偶性决定了对称差后黑色边数的变化奇偶性。

---

判无解的条件

如果 $s_0$ 为奇数，且 $G'$ 中所有环的权值和都是偶数，则无论如何调整都无法得到偶数黑色边匹配，此时无解。

这等价于：在 $G'$ 中，从任意点出发，到任意点的所有路径的权值奇偶性相同（即权值模2是“可定势”的）。
用并查集或BFS可检查。

---

算法步骤总结

1. 输入二分图，记录边编号和颜色。
2. 用匈牙利算法求任意完美匹配 $M_0$。如果不存在完美匹配，直接输出 -1。
3. 计算 $M_0$ 中黑色边数 $s_0$。
4. 若 $s_0$ 为偶数，输出 $M_0$ 的边编号。
5. 若 $s_0$ 为奇数：
   • 构造有向图 $G'$（匹配边反向，非匹配边正向）。
   • 用BFS/DFS找权值为奇数的环。
   • 若找到，对该环与 $M_0$ 作对称差，得到新匹配 $M_1$（黑色边数为偶数），输出 $M_1$。
   • 若找不到，输出 -1。

---

复杂度分析

• 匈牙利算法求完美匹配：$O(n^3)$ 或 $O(n m)$，因 $n \le 500$，$m \le n^2$，可接受。
• 构造 $G'$ 和找奇权环：$O(n+m)$。
• 总复杂度 $O(T \cdot n^3)$，在 $T \le 250$，$\sum n \le 500$ 时可行。

---

证明概要

定理：上述算法能找到解当且仅当存在偶黑色边完美匹配。

证明方向：

• 充分性：若算法找到环并调整，得到匹配且黑色边数为偶数。
• 必要性：若存在解 $M^*$，考虑 $M_0 \oplus M^*$。它由若干偶环组成（因为完美匹配的对称差是偶环的并）。
  在这些环中，至少有一个环的权值（黑色边数）为奇数（否则 $M_0$ 和 $M^*$ 的黑色边数奇偶性相同，矛盾）。
  因此算法在找奇权环时一定会找到。

---

特例与边界情况

• $n=2$ 时可能只有两条边，必须直接检查。
• 所有边同色时：如果全白，任意匹配都满足；如果全黑，要求匹配大小为偶数（即 $n$ 为偶数）才有解。
• 随机图（子任务3）：解存在的概率很高，因为奇偶性约束容易满足。

---

实现注意事项

• 边编号从1开始，输出时需映射回去。
• 二分图匹配需高效实现（邻接表+DFS匈牙利）。
• 找奇权环时用0/1 BFS或DFS染色（黑边权1，白边权0，模2意义下）。

---

总结

本题将匹配问题与模2线性约束结合，通过对称差调整改变奇偶性，转化为在有向图中找奇权环。
核心思想是利用匹配的结构性质（对称差为偶环），将全局奇偶约束局部化到环上处理。
算法复杂度适中，适合 $n \le 500$ 的数据范围。