题解：P11892 [XRCOI Round 1] C. 草萤有耀终非火

· · 题解

题目大意

有一个 n 行 m 列的网格，初始所有灯熄灭。给定 k 个有燃料的格子，这些格子可以被主动点燃（花费 1 代价），也可以被自动点亮。自动点亮的规则是：
若存在正整数 a, b, x, y 满足 1 \le x < x + a \le n，1 \le y < y + b \le m，且四个角 (x, y), (x + a, y), (x, y + b), (x + a, y + b) 的灯 中有三个已点亮，则另一个会自动点亮（不花费代价）。

目标：最终使 (1,1) 和 (1,m) 都被点亮。求最少需要主动点燃的燃料数，无解输出 -1。

思路

4pts

若 (1,1) 和 (1,m) 中本身就有燃料，则答案为 2；若 m=1，则答案为 1；若两者均无燃料或只有一个有燃料，则输出 -1。

若任意两个燃料格子既不在同一行也不在同一列，则同样输出 -1。

20pts

采用暴力搜索枚举所有可能情况。

AC 做法

从题目描述中可以感受到，本题与矩形的性质密切相关。目标点 (1,1) 和 (1,m) 位于同一行，因此问题很可能与行和列的结构有关。受此启发，我们可以将每一行和每一列分别视为图中的一个节点，若某个燃料格位于第 x 行第 y 列，则在代表第 x 行的节点与代表第 y 列的节点之间连一条无向边。

这样一来，问题就转化为：将第 1 行、第 1 列和第 m 列这三个节点连接成同一个连通块，并使得花费最小。这恰好与最小斯坦纳树（若不了解可点击这里喵）的思想相似，因此我们可以借鉴其处理方法。

对于三个终端节点，最小斯坦纳树的大小等价于 \min_{v} \big(\text{dist}(s_1,v)+\text{dist}(s_2,v)+\text{dist}(s_3,v)\big)，其中 s_1,s_2,s_3 分别为第 1 行、第 1 列和第 m 列对应的节点。因为任何连接这三个节点的树总存在一个中心节点，使得从它出发到三个终端的路径互不重叠，总边数即为三条最短路径长度之和；而任意一个 v 的三条最短路径的并集必定包含一棵连接三点的树，其大小不超过三距离之和，取最小值即可得到最优解。

具体实现时，我们分别以这三个节点为源点，进行三次 BFS（图中每条边权均为 1，BFS 等价于求最短路）。每次 BFS 记录从该源点到图上每个节点的最短距离。三次遍历完成后，枚举所有节点，计算它到三个源点的距离之和，取其中的最小值即为答案。

代码

这里我习惯用链式前向星存图，应该是比 vector 的做法要快一点。

::::info[代码]

/*
By Nongwu_
2026 / 8 / 7
给个关注呗 QwQ
不给关注给个赞也彳亍 TwT 
*/
#include<bits/stdc++.h>
#define Nongwu_ 0 
#define By return 
using namespace std;
using ll = long long ;
const int N = 2e5 + 10, INF = INT_MAX, M = 2e6 + 10;

int t, n, m, k;
int tot, head[N];
ll len[N], sum[N];
queue<int> q;

struct Edge{
    int next, to;
} e[M << 1];

void add(int x, int y) {
    e[++tot] = {head[x], y};
    head[x] = tot;
}

void bfs(int root) {
    for (int i = 1; i <= n + m; ++i)
        len[i] = INF;   //多测一定要清空口牙
    q.push(root);
    len[root] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].next) {
            int y = e[i].to;
            if (len[y] == INF) {
                len[y] = len[x] + 1;
                q.push(y);
            }
        }
    }
    for (int i = 1; i <= n + m; ++i)
        sum[i] += len[i];
}

void solve() {
    tot = 0;
    for (int i = 1; i <= n + m; ++i) {  //多测清空
        head[i] = 0;
        sum[i] = 0;
    }
    cin >> n >> m >> k;
    for (int i = 1, x, y; i <= k; ++i) {
        cin >> x >> y;
        add(x, y + n);
        add(y + n, x);
    }
    bfs(1);
    bfs(n + 1);
    bfs(n + m);
    ll ans = INF;
    for (int i = 1; i <= n + m; ++i)
        ans = min(ans, sum[i]);
    if (ans < INF)
        cout << ans << '\n';
    else
        cout << "-1\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> t;
    while (t--)
        solve();
    By Nongwu_;
}

::::

本文章经过 Deepseek 润色，作者保证本人贡献绝对大于 AI。