专栏文章

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

MMrkn_chenyx12
P14536题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min5t0wr
此快照首次捕获于
2025/12/01 21:02
3 个月前
此快照最后确认于
2025/12/01 21:02
3 个月前
查看原文

题目分析

对于每条边，仅有其两个端点上的路灯可以放倒在这里。对于一条长度为 LiL_i 的道路 (Ai,Bi)(A_i, B_i)，以下四种情况存在显然最优的方案：
  1. Li≥HAi+HBiL_i\ge H_{A_i}+H_{B_i}，Ai,BiA_i, B_i 上的路灯均放倒在这条道路上。
  2. Li≥HAi∧Li<HBiL_i\ge H_{A_i}\wedge L_i<H_{B_i}，AiA_i 上的路灯放倒在这条道路上。
  3. Li≥HBi∧Li<HAiL_i\ge H_{B_i}\wedge L_i<H_{A_i}，BiB_i 上的路灯放倒在这条道路上。
  4. Li<HAi∧Li<HBiL_i<H_{A_i}\wedge L_i<H_{B_i}，这条道路没有任何作用，当作不存在。
如果上述规则试图将某个路口上的路灯同时放倒到多条道路上，任选一条即可。
除上述四种情况以外，还有 Li≥HBi∧Li≥HAi∧Li<HAi+HBiL_i\ge H_{B_i}\wedge L_i\ge H_{A_i}\wedge L_i<H_{A_i}+H_{B_i} 的情况，此时仅能将 AiA_i 和 BiB_i 之一上的路灯放倒在这条道路上。
不难发现，如果将这类边建图，则对于每个连通分量：只要存在环，或存在被前文四种情况中的前三种覆盖到的点，就存在将所有点上的路灯放倒的方案，否则恰有一个点上的路灯无法被放倒。
考虑将边定向，被前文四种情况中的前三种覆盖到的点上的路灯已经放倒，其余有出度的点上的路灯向任意出边放倒，容易证得上述结论。
实际上我们并不需要真的建出这张图，只需要使用并查集维护连通分量，并记录是否可以放倒其中所有的点即可。
时间复杂度为 O((n+m)α(n))O((n+m)\alpha(n))。

参考实现

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...