P4292 [WC2010]重建计划点分治+单调队列

题目描述

题目传送门

分析

看到比值的形式就想到 \(01分数规划\)，二分答案

设当前的值为 \(mids\)

如果存在\(\frac{\sum _{e \in S} v(e)}{|S|} \geq mids\)

那么 \(\sum _{e \in S} v(e)-|S| \times mids \geq 0\)

我们把每一条边的权值减去 \(mids\)

问题就变成了找出一条长度在 \([l,r]\) 之间的简单路径

是的路径的长度大于等于 \(0\)

我们可以开一个权值线段树去维护，但这样复杂度就变成了 \(nlog^3n\)

实际上，我们可以把寻找路径时的 \(dfs\) 换成 \(bfs\)

这样就相当于自动给路径的长度排好了序，可以直接用单调队列维护

因为每一次单调队列都要从 \(0\) 枚举到 \(min(r,maxdep)\)

因为你记录最大值的数组最多只会更新到 \(maxdep\)，所以枚举多了没用

为了保证复杂度，我们要提前把子树按照子树内最大深度从小到大排序，使得 \(maxdep\) 尽可能小

还可以提前建出点分树，避免每一次 \(dfs\) 重新找重心浪费时间

时间复杂度 \(nlog^2n\)

代码

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<vector>

#define rg register

inline int read(){

	rg int x=0,fh=1;

	rg char ch=getchar();

	while(ch<'0' || ch>'9'){

		if(ch=='-') fh=-1;

		ch=getchar();

	}

	while(ch>='0' && ch<='9'){

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return x*fh;

}

const int maxn=4e5+5;

int h[maxn],tot=1,n,m,lef,rig;

struct asd{

	int to,nxt,preval;

	double val;

}b[maxn];

void ad(rg int aa,rg int bb,rg int cc){

	b[tot].to=bb;

	b[tot].nxt=h[aa];

	b[tot].preval=cc;

	h[aa]=tot++;

}

struct Node{

	int num,dep,id;

	Node(){}

	Node(rg int aa,rg int bb,rg int cc){

		num=aa,dep=bb,id=cc;

	}

};

std::vector<Node> pre[maxn];

bool cmp(rg Node aa,rg Node bb){

	return aa.dep<bb.dep;

}

int dep[maxn];

void dfs(rg int now,rg int lat,rg int nowdep){

	dep[now]=nowdep;

	for(rg int i=h[now];i!=-1;i=b[i].nxt){

		rg int u=b[i].to;

		if(u==lat) continue;

		dfs(u,now,nowdep+1);

		dep[now]=std::max(dep[now],dep[u]);

	}

}//预处理子树最大深度

int siz[maxn],maxsiz[maxn],rt,totsiz,jud[maxn],tim,tp;

bool vis[maxn];

std::vector<int> g[maxn];

void getroot(rg int now,rg int lat){

	siz[now]=1,maxsiz[now]=0;

	for(rg int i=h[now];i!=-1;i=b[i].nxt){

		rg int u=b[i].to;

		if(u==lat || vis[u]) continue;

		getroot(u,now);

		siz[now]+=siz[u];

		maxsiz[now]=std::max(maxsiz[now],siz[u]);

	}

	maxsiz[now]=std::max(maxsiz[now],totsiz-siz[now]);

	if(maxsiz[now]<maxsiz[rt]) rt=now;

}//找重心

void predfs(rg int now){

	vis[now]=1;

	for(rg int i=h[now];i!=-1;i=b[i].nxt){

		rg int u=b[i].to;

		if(!vis[u]){

			pre[now].push_back(Node(u,dep[u],i));

		}

	}

	std::sort(pre[now].begin(),pre[now].end(),cmp);

	for(rg int i=0;i<pre[now].size();i++){

		rg int u=pre[now][i].num;

		totsiz=siz[u],rt=0;

		getroot(u,now);

		g[now].push_back(rt);

		predfs(rt);

	}

}//建好点分树，并按照最大深度从小到大排序

double ans=-1e7,mmax[maxn];

struct jie{

	double val;

	int dep;

	jie(){}

	jie(rg double aa,rg int bb){

		val=aa,dep=bb;

	}

}sta[maxn];

int q1[maxn],q2[maxn],nhead,ntail;

double q3[maxn];

void bfs(rg int now,rg double nval,rg int ndep){

	tim++;

	jud[now]=tim,nhead=ntail=1;

	q1[1]=now,q2[1]=ndep,q3[1]=nval;

	rg int now1,now2;

	rg double now3;

	while(nhead<=ntail){

		now1=q1[nhead],now2=q2[nhead],now3=q3[nhead];

		sta[++tp]=jie(now3,now2);

		nhead++;

		for(rg int i=h[now1];i!=-1;i=b[i].nxt){

			rg int u=b[i].to;

			if(jud[u]==tim || vis[u]) continue;

			jud[u]=tim;

			ntail++;

			q1[ntail]=u,q2[ntail]=now2+1,q3[ntail]=now3+b[i].val;

		}

	}

}//bfs寻找路径

int q[maxn],head,tail;

void solve(rg int now){

	vis[now]=1,tp=1;

	rg int beg=0,cs=0,tl=0,tr=0,maxdep=0;

	mmax[0]=0;

	for(rg int i=0;i<pre[now].size();i++){

		rg int u=pre[now][i].num;

		beg=tp+1;

		bfs(u,b[pre[now][i].id].val,1);

		head=1,tail=0,cs=beg;

		for(rg int j=std::min(rig,maxdep);j>=0;j--){

			tl=j>=lef?0:lef-j,tr=rig-j;

			while(head<=tail && sta[q[head]].dep<tl) head++;

			while(cs<=tp && sta[cs].dep<tl) cs++;

			while(cs<=tp && sta[cs].dep<=tr){

				while(head<=tail && sta[cs].val>=sta[q[tail]].val) tail--;

				q[++tail]=cs++;

			}

			if(head<=tail) ans=std::max(ans,sta[q[head]].val+mmax[j]);

		}

		for(rg int j=beg;j<=tp;j++) mmax[sta[j].dep]=std::max(mmax[sta[j].dep],sta[j].val);

		maxdep=std::max(maxdep,sta[tp].dep);

	}

	if(ans>=0) return;

	for(rg int i=1;i<=tp;i++) mmax[sta[i].dep]=-1e9;

	for(rg int i=0;i<g[now].size();i++) solve(g[now][i]);

}//点分治核心+单调队列

bool pd(rg double mids){

	memset(vis,0,sizeof(vis));

	memset(jud,0,sizeof(jud));

	for(rg int i=0;i<maxn;i++) mmax[i]=-1e7;

	ans=-1e7,tim=0;

	for(rg int i=1;i<tot;i++) b[i].val=(double)b[i].preval-mids;

	solve(rt);

	return ans>=0;

}//判断答案是否合法

int main(){

	memset(h,-1,sizeof(h));

	n=read(),lef=read(),rig=read();

	rg int aa,bb,cc;

	for(rg int i=1;i<n;i++){

		aa=read(),bb=read(),cc=read();

		ad(aa,bb,cc);

		ad(bb,aa,cc);

	}

	dfs(1,0,0);

	maxsiz[0]=0x3f3f3f3f,rt=0,totsiz=n;

	getroot(1,0);

	predfs(rt);

	totsiz=n,rt=0;

	memset(vis,0,sizeof(vis));

	getroot(1,0);

	double l=0,r=1e6,mids;

	for(rg int i=1;i<=33;i++){

		mids=(l+r)/2.0;

		if(pd(mids)) l=mids;

		else r=mids;

	}

	printf("%.3f\n",mids);

	return 0;

}

巴特西

P4292 [WC2010]重建计划点分治+单调队列

题目描述

分析

代码

最新文章

热门文章

巴特西

P4292 [WC2010]重建计划 点分治+单调队列

题目描述

分析

代码

最新文章

热门文章

P4292 [WC2010]重建计划点分治+单调队列