2026 杭电春季联赛 2——1002-庭扫落樱（二分图最大匹配）

题目大意

题目描述

给定二维平面第一象限上的 $n$ 个弹幕发射器。第 $i$ 个发射器位于坐标 $(x_i, y_i)$，并向四个方向之一发射一条射线（激光）：

• $d_i = 0$：向上发射

• $d_i = 1$：向右发射

• $d_i = 2$：向下发射

• $d_i = 3$：向左发射

射线的照明路径包含发射器本身所在的位置。题目保证任意两个发射器不会同时在对方的照明路径上。

现在可以在平面上放置障碍物（允许放置在发射器所在的坐标上），只要障碍物位于某条射线上，就能阻挡该射线的照射。求最少需要放置多少个障碍物，才能使得所有 $n$ 个发射器的照射路径上都至少包含一个障碍物。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。

每个测试用例第一行包含一个整数 $n$（$1 \le n \le 300$），表示发射器的数量。
接下来 $n$ 行，每行包含三个整数 $x_i, y_i, d_i$（$1 \le x_i, y_i \le 10^9$，$d_i \in \{0, 1, 2, 3\}$），表示发射器的坐标与发射方向。

保证所有测试用例中 $n$ 的总和不超过 $3000$。

输出格式

对于每个测试用例，输出一行一个整数，表示最少需要放置的障碍物数量。

样例输入

2
6
5 5 0
3 7 1
9 9 2
9 1 3
5 2 0
1 20 3
1
1 1 0

样例输出

3
1

样例解释

在第一个测试用例中，有 $6$ 个发射器。一种最优方案是放置 $3$ 个障碍物，具体位置如下：

1. 在坐标 $(5, 7)$ 处放置一个障碍物：该点覆盖了第 $1$ 束（从 $(5,5)$ 向上）、第 $2$ 束（从 $(3,7)$ 向右）以及第 $5$ 束（从 $(5,2)$ 向上）激光。

2. 在坐标 $(9, 1)$ 处放置一个障碍物：该点覆盖了第 $3$ 束（从 $(9,9)$ 向下）以及第 $4$ 束（从 $(9,1)$ 向左）激光。

3. 在坐标 $(-2025, 20)$ 处放置一个障碍物：该点覆盖了第 $6$ 束（从 $(1,20)$ 向左）激光。

该方案共使用了 $3$ 个障碍物，且可以证明不存在比 $3$ 更少的放置方案。

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）