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

简单题，场切了。

首先考虑边权全部为

1

且路灯的高度全部为

1

的时候该怎么做？

对于一个连通块，如果它是一棵树，那么只能有

n-1

条边可以拿来放，否则一定可以将

n

个路灯全部放倒，正确性显然。

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

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

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

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

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

Code:

CPP

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

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

文章操作

相关推荐

评论

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