题解：P14536 [OII 2025] 路灯收集 / Raccogli i lampioni

· · 题解

题目分析

对于每条边，仅有其两个端点上的路灯可以放倒在这里。对于一条长度为 L_i 的道路 (A_i, B_i)，以下四种情况存在显然最优的方案：

如果上述规则试图将某个路口上的路灯同时放倒到多条道路上，任选一条即可。

除上述四种情况以外，还有 L_i\ge H_{B_i}\wedge L_i\ge H_{A_i}\wedge L_i<H_{A_i}+H_{B_i} 的情况，此时仅能将 A_i 和 B_i 之一上的路灯放倒在这条道路上。

不难发现，如果将这类边建图，则对于每个连通分量：只要存在环，或存在被前文四种情况中的前三种覆盖到的点，就存在将所有点上的路灯放倒的方案，否则恰有一个点上的路灯无法被放倒。

考虑将边定向，被前文四种情况中的前三种覆盖到的点上的路灯已经放倒，其余有出度的点上的路灯向任意出边放倒，容易证得上述结论。

实际上我们并不需要真的建出这张图，只需要使用并查集维护连通分量，并记录是否可以放倒其中所有的点即可。

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

参考实现

#include <bits/stdc++.h>
using namespace std;

int fa[1000024];
char r[1000024];

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) r[x] = 1;
    else fa[y] = x, r[x] |= r[y];
}

int illumina(int n, int m, vector<int> h, vector<int> A, vector<int> B, vector<int> L) {
    for (int i = 0; i < n; i++) fa[i] = i;
    for (int i = 0; i < m; i++) {
        int a = A[i], b = B[i], l = L[i];
        if (l >= h[a] + h[b]) r[find(a)] = 1, r[find(b)] = 1;
        else if (l >= h[a] && l >= h[b]) merge(a, b);
        else if (l >= h[a]) r[find(a)] = 1;
        else if (l >= h[b]) r[find(b)] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) if (fa[i] == i && !r[i]) ans++;
    return n - ans;
}