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

Little_Fox_Fairy · 2025-11-21 16:45:03 · 题解

简单题，场切了。

首先考虑边权全部为 1 且路灯的高度全部为 1 的时候该怎么做？

对于一个连通块，如果它是一棵树，那么只能有 n-1 条边可以拿来放，否则一定可以将 n 个路灯全部放倒，正确性显然。

我们考虑如何将图转化成上面的这种形式？

首先对于一个点，如果它有一条边使得这条边两头的点都可以倒在这条这条边上，或者只有这个点可以倒在这条边上，那么直接把这个点倒在这条边上即可。

因为你把这个点倒在这条边上对于另外一个点是没有影响的，所以直接倒就是对的。

然后考虑剩下的点之间的关系：只剩下一条边只有一个点可以倒下的情况（两个点都倒不下算不了贡献）。

我们把这些剩下的边拉出来建一个新图，然后跑上面那个算法即可。

Code:

#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=1e6+10;

int n,m,a[N];
int w[N];
vector<pii> e[N];
vector<int> g[N];
bitset<N> vis;
bitset<N> down;
int res=0;
void dfs(int u) {
    vis[u]=1;
    for (auto v : e[u]) if (a[u]+a[v.first]>w[v.second] and a[u]<=w[v.second] and a[v.first]<=w[v.second]) g[u].eb(v.first);
    for (auto v : e[u]) {
        if ((a[v.first]>w[v.second] and a[u]<=w[v.second]) or a[u]+a[v.first]<=w[v.second]) down[u]=1;
        if (vis[v.first]) continue;
        dfs(v.first);
    }
    return ;
}
bool can=0;
int cnt=0,tot=0;
void dfz(int u) {
    can|=down[u],cnt++;
    vis[u]=1;
    tot+=g[u].size();
    for (auto v : g[u]) {
        if (vis[v]) continue;
        dfz(v);
    }
    return ;
}
int illumina(int N,int M,vector<int> H,vector<int> A,vector<int> B,vector<int> L) {
    n=N,m=M;
    rep(i,1,n) a[i]=H[i-1];
    rep(i,1,m) {
        int u,v,x;u=A[i-1],v=B[i-1],x=L[i-1];
        u++,v++,w[i]=x;
        e[u].eb(v,i),e[v].eb(u,i);
    }
    rep(i,1,n) if (!vis[i]) dfs(i);
    vis.reset();
    rep(i,1,n) if (!vis[i]) {
        if (g[i].empty()) {
            res+=down[i];
            continue;
        }
        can=0,cnt=0,tot=0;
        dfz(i);
        if (tot/2>cnt-1) can=1;
        res+=cnt-1+can;
    } 
    return res;
}