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

CHNcen · 2026-08-05 13:30:05 · 题解

由于特殊操作的前置条件类似于矩形的边限制，考虑将原图的行与列抽象为节点，每个装有燃料的灯 (x,y) 对应一条连接第 x 行节点与第 y 列节点的无向边。

此时目标转变为使第 1 行，第 1 列与第 m 列对应节点连通。对于三个目标节点，所需的最少边数就是它们在图中的斯坦纳树大小。又由于边权为 1，则最优解一定可以表示为一个中间节点 x，使得三个目标节点到 x 的最短路径之和最小。因此分别以三个节点为起点跑最短路，计算 \sum dis 并取最小值即可。

时间复杂度 O(\sum (n + m))。

#include<bits/stdc++.h>
#define LoveFurina ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F(x, l, r) for(int x = l; x <= r; ++x)
#define B(x, r, l) for(int x = r; x >= l; --x)
#define ll long long
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f;

int T;
int n, m, k;
vector<int> adj[N << 1];

queue<int> q;
bool vis[N << 1];
int dis[N << 1];

int cnt[N << 1];

inline void addedge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

inline void SPFA(int s) {
    F (i, 1, n + m) vis[i] = 0, dis[i] = INF;

    q.push(s);
    vis[s] = 1, dis[s] = 0;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = 0;
        for (auto &v : adj[u]) {
            if (dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }

    F (i, 1, n + m) cnt[i] += dis[i];
}

int main() {
    LoveFurina;

    cin >> T;
    while (T--) {
        cin >> n >> m >> k;
        F (i, 1, n + m) cnt[i] = 0, adj[i].clear();

        F (i, 1, k) {
            int x, y; cin >> x >> y;
            addedge(x, n + y);
        }

        SPFA(1);
        SPFA(n + 1);
        SPFA(n + m);

        int ans = INF;
        F (i, 1, n + m) ans = min(ans, cnt[i]);
        cout << (ans >= INF ? -1 : ans) << '\n';
    }

return 0;
}