WC2010重建计划

2014年12月3日7,5142

Description

Input

第一行包含一个正整数N，表示X国的城市个数. 第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号

Output

输出最大平均估值，保留三位小数

Sample Input

4
2 3
1 2 1
1 3 2
1 4 3

Sample Output

2.500

HINT

20%的数据,N<=5000
30%的数据,N<=100000,原有方案恰好为一条路径
100%的数据,N<=100000,1<=L<=U<=N-1,Vi<=1000000

题解

点分治

对于每个重心，二分一个答案mid

将图中所有边减mid，问题转换为判断是否存在长为x的路径，路径边权和>=0，L<=x<=U

从重心剖开树以后，得到若干棵子树

顺序处理每棵子树，并维护mx[i]表示起点从重心出发，终点在子树内，长度为i的路径边权和最值

对于一棵子树，bfs得其所有路径长度及边权和（起点从重心出发，终点在该子树内）

由于是bfs，所以路径长度是从小到大

mx倒序是从大到小

枚举路径i，维护mx的单调递减队列(dis)

若当前mx+deep[i]>=L则mx加入队尾（维护单调）

若deep[i]+q[l]>U，则l++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<ctime>
#include<vector>
#include<set>
#include<cmath>
#include<algorithm>
#define inf 1000000000
#define ll long long
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,cnt,S,L,U,root,lim;
double ans;
struct edge{int to,next,v;}e[200005];int last[200005];
int size[100005],fa[100005],f[100005],deep[100005];
int q[100005],dq[100005];
bool mark[100005];
double dis[100005],mx[100005];
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}
void getroot(int x,int fa)
{
	size[x]=1;f[x]=0;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa&&!mark[e[i].to])
		{
			getroot(e[i].to,x);
			size[x]+=size[e[i].to];
			f[x]=max(f[x],size[e[i].to]);
		}
	f[x]=max(f[x],S-size[x]);
	if(f[x]<=f[root])root=x;
}
bool jud(int rt,double M)
{
	int up=0;
	for(int t=last[rt];t;t=e[t].next)
	{
		if(mark[e[t].to])continue;
		int head=0,tail=1;
		q[0]=e[t].to;
		fa[e[t].to]=root;deep[e[t].to]=1;
		dis[e[t].to]=(double)e[t].v-M;
		while(head!=tail)
		{
			int now=q[head];head++;
			for(int i=last[now];i;i=e[i].next)
				if(e[i].to!=fa[now]&&!mark[e[i].to])
				{
					q[tail]=e[i].to;
					fa[e[i].to]=now;deep[e[i].to]=deep[now]+1;
					dis[e[i].to]=dis[now]+e[i].v-M;
					tail++;
				}
		}
		int l=1,r=0,now=up;
		for(int i=0;i<tail;i++)
		{
			int x=q[i];
			while(deep[x]+now>=L&&now>=0)
			{
				while(l<=r&&mx[dq[r]]<mx[now])r--;
				dq[++r]=now;
				now--;
			}
			while(l<=r&&deep[x]+dq[l]>U)l++;
			if(l<=r&&dis[x]+mx[dq[l]]>=0)return 1;
		}
		for(int i=up+1;i<=deep[q[tail-1]];i++)mx[i]=-inf;
		for(int i=0;i<tail;i++)
		{
			int x=q[i];
			mx[deep[x]]=max(mx[deep[x]],dis[x]);
		}
		up=max(up,deep[q[tail-1]]);
	}
	return 0;
}
void cal(int x)
{
	double l=ans,r=lim,mid;
	while(r-l>0.0001)
	{
		mid=(l+r)/2;
		if(jud(x,mid))l=mid;
		else r=mid;
	}
	ans=l;
}
void solve(int x)
{
	cal(x);
	mark[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(!mark[e[i].to])
		{
			root=0;S=size[e[i].to];
			getroot(e[i].to,0);
			if(size[e[i].to]>L)
				solve(root);
		}
}
int main()
{
	freopen("rebuild.in","r",stdin);
	freopen("rebuild.out","w",stdout);
	n=read();L=read();U=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read(),w=read();
		insert(u,v,w);
		lim=max(lim,w);
	}
	f[0]=n;
	root=0;S=n;
	getroot(1,0);
	solve(root);
	printf("%.3lf",ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<map>

#include<ctime>

#include<vector>

#include<set>

#include<cmath>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,cnt,S,L,U,root,lim;

double ans;

struct edge{int to,next,v;}e[200005];int last[200005];

int size[100005],fa[100005],f[100005],deep[100005];

int q[100005],dq[100005];

bool mark[100005];

double dis[100005],mx[100005];

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;

}

void getroot(int x,int fa)

{

size[x]=1;f[x]=0;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa&&!mark[e[i].to])

{

getroot(e[i].to,x);

size[x]+=size[e[i].to];

f[x]=max(f[x],size[e[i].to]);

}

f[x]=max(f[x],S-size[x]);

if(f[x]<=f[root])root=x;

}

bool jud(int rt,double M)

{

int up=0;

for(int t=last[rt];t;t=e[t].next)

{

if(mark[e[t].to])continue;

int head=0,tail=1;

q[0]=e[t].to;

fa[e[t].to]=root;deep[e[t].to]=1;

dis[e[t].to]=(double)e[t].v-M;

while(head!=tail)

{

int now=q[head];head++;

for(int i=last[now];i;i=e[i].next)

if(e[i].to!=fa[now]&&!mark[e[i].to])

{

q[tail]=e[i].to;

fa[e[i].to]=now;deep[e[i].to]=deep[now]+1;

dis[e[i].to]=dis[now]+e[i].v-M;

tail++;

}

int l=1,r=0,now=up;

for(int i=0;i<tail;i++)

{

int x=q[i];

while(deep[x]+now>=L&&now>=0)

{

while(l<=r&&mx[dq[r]]<mx[now])r--;

dq[++r]=now;

now--;

}

while(l<=r&&deep[x]+dq[l]>U)l++;

if(l<=r&&dis[x]+mx[dq[l]]>=0)return 1;

}

for(int i=up+1;i<=deep[q[tail-1]];i++)mx[i]=-inf;

for(int i=0;i<tail;i++)

{

int x=q[i];

mx[deep[x]]=max(mx[deep[x]],dis[x]);

}

up=max(up,deep[q[tail-1]]);

}

return 0;

}

void cal(int x)

{

double l=ans,r=lim,mid;

while(r-l>0.0001)

{

mid=(l+r)/2;

if(jud(x,mid))l=mid;

else r=mid;

}

ans=l;

}

void solve(int x)

{

cal(x);

mark[x]=1;

for(int i=last[x];i;i=e[i].next)

if(!mark[e[i].to])

{

root=0;S=size[e[i].to];

getroot(e[i].to,0);

if(size[e[i].to]>L)

solve(root);

}

int main()

{

freopen("rebuild.in","r",stdin);

freopen("rebuild.out","w",stdout);

n=read();L=read();U=read();

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

{

int u=read(),v=read(),w=read();

insert(u,v,w);

lim=max(lim,w);

}

f[0]=n;

root=0;S=n;

getroot(1,0);

solve(root);

printf("%.3lf",ans);

return 0;

}

« 「CF492D」Vanya and Computer Game 「BZOJ2732」[HNOI2012] 射箭 »

春风不识路

黄学长，貌似这一题在加了一组数据后您的程序会TLE ρ(・ω・、)

小轮子

黄学长，树的点分治+单调队列不是n^2的么

Kaiser

n log ^2n

Kaiser

没有对深度排序是n^2的

hzwer.com _ Home | http://hzwer.com

WC2010重建计划

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论