2026 杭电春季联赛 2——1002-庭扫落樱(二分图最大匹配)(最小边覆盖和最大匹配之间的关系) · znzryb
## 题目大意
**题目描述**
给定二维平面第一象限上的 $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)$ 向上)激光。
1. 在坐标 $(9, 1)$ 处放置一个障碍物:该点覆盖了第 $3$ 束(从 $(9,9)$ 向下)以及第 $4$ 束(从 $(9,1)$ 向左)激光。
1. 在坐标 $(-2025, 20)$ 处放置一个障碍物:该点覆盖了第 $6$ 束(从 $(1,20)$ 向左)激光。
该方案共使用了 $3$ 个障碍物,且可以证明不存在比 $3$ 更少的放置方案。
## 思路讲解
一种错误的图论建模方式是把激光当作左边的点,把这个障碍物当成右边的点,但是这样子建图是做不出来这道题目的,因为我们不是要让激光和障碍物一一匹配,这个非常容易就能做到。
[P3386 【模板】二分图最大匹配](/2024/10/18/20241018-f95d8db4)
那么要做这道题目,最重要的就是**我们要把障碍物看成连边,左边的点指的是这个方向为上下的点,右边的点指的是这个方向为左右的点**。

```cpp
void Solve() {
ll N;
cin >> N;
vector<X_y_d> xyd_ls(N);
for (int i = 0; i < N; ++i) {
cin >> xyd_ls[i].x >> xyd_ls[i].y >> xyd_ls[i].d;
}
xyd_ls = unique_xyd_ls(xyd_ls);
auto g = build_graph(xyd_ls);
Bi_graph_matcher matcher(g,SZ(xyd_ls));
ll mx_match = matcher.mx_match();
ll ans = (SZ(xyd_ls) - 2 * mx_match) + mx_match;
cout << ans << "\n";
}
```
## AC代码
AC
[https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=18859](https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=18859)
::: 源代码
```cpp
// teamname: Gospel_rock
/**
* Problem: 庭扫落樱
* Contest:
* Judge: HDOJ
* URL: https://acm.hdu.edu.cn/contest/problem?cid=1198&pid=1002
* Created: 2026-03-29 18:54:03
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#include <utility>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);
ll lT, testcase;
/*
*
*/
struct X_y_d {
ll x;
ll y;
ll d;
};
struct X_y {
ll x;
ll y;
bool operator<(const X_y &o) const {
if (x != o.x) return x < o.x;
return y < o.y;
}
};
bool is_two_laser_intersect(X_y_d a, X_y_d b) {
if ((a.d==0 || a.d==2) && (b.d==1 || b.d==3)) {
X_y node = {a.x, b.y};
if (a.d == 0) {
if (node.y < a.y) {
return false;
}
}
if (a.d == 2) {
if (node.y > a.y) {
return false;
}
}
if (b.d == 1) {
if (node.x < b.x) {
return false;
}
}
if (b.d == 3) {
if (node.x > b.x) {
return false;
}
}
return true;
}else {
return false;
}
}
auto unique_xyd_ls_detail(const vector<X_y_d> &xyd_ls, ll offset) {
vector<X_y_d> res;
res.reserve(SZ(xyd_ls));
map<ll, ll> mp1, mp3;
for (auto [x,y,d]: xyd_ls) {
if (offset) {
swap(x, y);
}
if (d == 0 + offset) {
if (!mp1.contains(x)) {
mp1[x] = y;
} else {
mp1[x] = max(mp1[x], y);
}
} else if (d == 2 + offset) {
if (!mp3.contains(x)) {
mp3[x] = y;
} else {
mp3[x] = min(mp3[x], y);
}
}
}
for (auto [x_,y_]: mp1) {
auto [x,y] = make_tuple(x_, y_);
if (offset) swap(x, y);
res.push_back({x, y, 0 + offset});
}
for (auto [x_,y_]: mp3) {
auto [x,y] = make_tuple(x_, y_);
if (offset) swap(x, y);
res.push_back({x, y, 2 + offset});
}
return res;
}
auto unique_xyd_ls(const vector<X_y_d> &xyd_ls) {
auto res1 = unique_xyd_ls_detail(xyd_ls, 0);
auto res2 = unique_xyd_ls_detail(xyd_ls, 1);
res1.insert(res1.end(), res2.begin(), res2.end());
#ifdef LOCAL
cerr << "xyd_ls:\n";
for (int i = 0; i < SZ(xyd_ls); ++i) {
cerr << xyd_ls[i].x << " " << xyd_ls[i].y << " " << xyd_ls[i].d << "\n";
}
#endif
return res1;
}
// 注意,二分图构建的是有向图
auto build_graph(const vector<X_y_d> &xyd_ls) {
ll idx = SZ(xyd_ls);
map<X_y, ll> mp;
vector<vector<ll> > g(SZ(xyd_ls) + 2);
for (int i = 0; i < SZ(xyd_ls); ++i) {
for (int j = i + 1; j < SZ(xyd_ls); ++j) {
if (xyd_ls[i].d == 0 || xyd_ls[i].d == 2) {
auto flag = is_two_laser_intersect(xyd_ls[i], xyd_ls[j]);
if (!flag) {
continue;
}
g[i].push_back(j);
}
}
}
// #ifdef LOCAL
// debug2d(g);
// #endif
return g;
}
struct Bi_graph_matcher {
vector<vector<ll> > g;
vector<char> vis;
vector<ll> match;
ll left_cnt;
Bi_graph_matcher(vector<vector<ll> > _g, ll _left_cnt) : g(std::move(_g)), vis(SZ(g) + 2), match(SZ(g) + 2, -1),
left_cnt(_left_cnt) {
}
bool find(ll u) {
for (auto to: g[u]) {
if (vis[to]) {
continue;
}
vis[to] = true;
// 如果 v 还没有匹配,或者 v 原本匹配的人能找到新的匹配(腾出位置)
if (match[to] == -1 || find(match[to])) {
match[to] = u;
return true;
}
}
return false;
}
ll mx_match() {
ll ans = 0;
for (int i = 0; i <= left_cnt; ++i) {
vis.assign(SZ(g) + 2, 0);
if (find(i)) {
++ans;
}
}
return ans;
}
};
void Solve() {
ll N;
cin >> N;
vector<X_y_d> xyd_ls(N);
for (int i = 0; i < N; ++i) {
cin >> xyd_ls[i].x >> xyd_ls[i].y >> xyd_ls[i].d;
}
xyd_ls = unique_xyd_ls(xyd_ls);
auto g = build_graph(xyd_ls);
Bi_graph_matcher matcher(g,SZ(xyd_ls));
ll mx_match = matcher.mx_match();
ll ans = (SZ(xyd_ls) - 2 * mx_match) + mx_match;
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
// auto start = std::chrono::high_resolution_clock::now();
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=18859
pair<bool, X_y> intersect_two_laser(X_y_d a, X_y_d b) {
// pair<bool, > res;
if (a.d == b.d) return {false, {}};
if (a.d == 0 && b.d == 2) return {false, {}};
if (a.d == 1 && b.d == 3) return {false, {}};
if ((a.d==0 && b.d==1)) {
}
X_y node = {a.x, b.y};
if (a.d == 0) {
if (node.y < a.y) {
return {false, {}};
}
}
if (a.d == 2) {
if (node.y > a.y) {
return {false, {}};
}
}
if (a.d == 1) {
if (node.x < a.x) {
return {false, {}};
}
}
if (a.d == 3) {
if (node.x > a.x) {
return {false, {}};
}
}
return {true, node};
}
// 注意,二分图构建的是有向图
auto build_graph(const vector<X_y_d> &xyd_ls) {
ll idx = SZ(xyd_ls);
map<X_y, ll> mp;
vector<vector<ll> > g(SZ(xyd_ls) + 2);
g.reserve(4 * SZ(xyd_ls));
for (int i = 0; i < SZ(xyd_ls); ++i) {
X_y xy = {xyd_ls[i].x, xyd_ls[i].y};
ll node;
if (mp.contains(xy)) {
node = mp[xy];
} else {
++idx;
g.push_back({});
node = idx;
mp[xy] = idx;
}
g[i].push_back(node);
// g[node].push_back(i);
}
for (int i = 0; i < SZ(xyd_ls); ++i) {
for (int j = i + 1; j < SZ(xyd_ls); ++j) {
auto [flag,xy] = intersect_two_laser(xyd_ls[i], xyd_ls[j]);
if (!flag) {
continue;
}
ll node;
if (mp.contains(xy)) {
node = mp[xy];
} else {
++idx;
g.push_back({});
node = idx;
mp[xy] = idx;
}
g[i].push_back(node);
g[j].push_back(node);
// g[node].push_back(i);
// g[node].push_back(j);
}
}
#ifdef LOCAL
debug2d(g);
#endif
return g;
}
*/
```
:::
## 心路历程(WA,TLE,MLE……)
最好显式忽略这个其他情况:

使用 offset 进行 swap,最后也要 swap 回来。

将哨兵值设置为 -1,可以避免 0-based 造成问题。
