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$ 更少的放置方案。

思路讲解

一种错误的图论建模方式是把激光当作左边的点，把这个障碍物当成右边的点，但是这样子建图是做不出来这道题目的，因为我们不是要让激光和障碍物一一匹配，这个非常容易就能做到。

P3386 【模板】二分图最大匹配

那么要做这道题目，最重要的就是我们要把障碍物看成连边，左边的点指的是这个方向为上下的点，右边的点指的是这个方向为左右的点。

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

源代码

// 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 造成问题。