【BZOJ 1758】 [Wc2010]重建计划

1758: [Wc2010]重建计划

Time Limit: 40 Sec   Memory Limit: 162 MB
Submit: 989   Solved: 345
[ Submit][ Status]

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

01分数规划+点分治。

做这道题的时候先看30%的数据，01分数规划+队列优化dp很好做。

那么对于一棵树呢？

用点分治来做就可以了！

01分数规划就是二分答案ans,然后把边权设为ans-原边权，若最小边权和小于0，那么增大ans，反之减小ans。

考虑经过根结点的（边权是更新过的）最小边权和：

枚举每一棵子树，用队列优化的dp来计算他与已经计算过的子树的满足>=l,<=u的最小边权和。

再递归处理每一个儿子。

于是整棵树的最小边权和就求出来了，若<=0，那么增大ans，反之减小ans。

直接这样写，TLE了5个点。

优化：

1.把二分写在点分治里面：

处理每一棵子树之前先二分求出经过当前树根的ans，在以后二分的时候把下界直接设成ans。

2.二分的时候根据优化1，可以感觉到最后的结果是偏向下界的，所以把mid=(l*19+r)/20

加上这些优化还是TLE了两个点TAT!!

求帮助。。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define eps 1e-4
#define ld long double
#define M 100005
#define inf 0x3f3f3f3f
using namespace std;
bool f;
int tt=0;
int h[M],n,aa,aaa,tot,now,ti=0,s[M],l,u,ma[M],root,size,siz,done[M];
ld ans,Ans,a[M],b[M],c[M],mm=0.00;
struct edge
{
	int y,ne;
	ld v;
}e[M*3];
struct Q
{
	ld v;
	int p;
}q[M];
void Addedge(int x,int y,ld v)
{
	e[++tot].y=y;
	e[tot].v=v;
	e[tot].ne=h[x];
	h[x]=tot;
}
void read(int &tmp)
{
	tmp=0;
	int fu=1;
	char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())
		if (ch=='-') fu=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())
		tmp=tmp*10+ch-'0';
	tmp*=fu;
}
void Getroot(int x,int fa)
{
	ma[x]=0,s[x]=1;
	for (int i=h[x];i;i=e[i].ne)
	{
		int y=e[i].y;
		if (y==fa||done[y]) continue;
		Getroot(y,x);
		s[x]+=s[y];
		if (ma[x]<s[y]) ma[x]=s[y];
	}
	if (ma[x]<siz-s[x]) ma[x]=siz-s[x];
	if (ma[x]<ma[root]) root=x;
}
int Getsize(int x,int fa)
{
	s[x]=1;
	for (int i=h[x];i;i=e[i].ne)
	{
		int y=e[i].y;
		if (done[y]||y==fa) continue;
		s[x]+=Getsize(y,x);
	}
	return s[x];
}
void dfs(ld k,int x,int fa,int dep)
{
	if (dep>u) return;
	for (int i=h[x];i;i=e[i].ne)
	{
		int y=e[i].y;
		if (done[y]||y==fa) continue;
		c[y]=c[x]+k-e[i].v;
		if (c[y]<b[dep]) b[dep]=c[y];
		dfs(k,y,x,dep+1);
	}
	if (dep>aa) aa=dep;
}
void dp()
{
	int ql=1,qr=0;
	for (int i=aaa;i>=l;i--)
	{
		while (ql<=qr&&a[i]<=q[qr].v)
			qr--;
		q[++qr].v=a[i],q[qr].p=i;
	}
	for (int i=0;i<=aa;i++)
	{
		if (q[ql].p==u-i+1) ql++;
		if (ql<=qr&&ans>q[ql].v+b[i]) ans=q[ql].v+b[i];
		if (i>=l) continue;
		while (ql<=qr&&a[l-i-1]<=q[qr].v)
			qr--;
		q[++qr].v=a[l-i-1],q[qr].p=l-i-1;
	}
}
ld Solve(int x,ld k)
{
	ans=inf;
	b[0]=0,a[0]=0;
	aaa=0,aa=0;
	for (int i=1;i<=u;i++)
		b[i]=a[i]=inf;
	for (int i=h[x];i;i=e[i].ne)
	{
		int y=e[i].y;
		if (done[y]) continue;
		b[1]=c[y]=k-e[i].v;
		aa=0;
		dfs(k,y,x,2);
		dp();
		if (ans<=0.00) {f=true;return ans;}
		for (int j=1;j<=u;j++)
			if (b[j]<a[j]) a[j]=b[j],b[j]=inf;
		if (aa>aaa) aaa=aa;
	}
	return ans;
}
void Work(int x,int size)
{
	if (size-1<l)
	{
		done[x]=1;
		return;
	}
	ld L=Ans,R=mm;
	while (R-L>eps)
	{
		ld mid=(L*19.0+R)/(20.0);
		if (Solve(x,mid)<=0) L=mid;
		else R=mid;
	}
	Ans=L;
	done[x]=1;
	for (int i=h[x];i;i=e[i].ne)
	{
		int y=e[i].y;
		if (done[y]) continue;
        siz=Getsize(y,0);
		root=0,ma[0]=inf;
		Getroot(y,0);
		Work(root,siz);
	}
}
int main()
{
        read(n),read(l),read(u);
	for (int i=1;i<n;i++)
	{
		int x,y,v;
		read(x),read(y),read(v);
		if ((ld)v>mm) mm=v;
		Addedge(x,y,(ld)v),Addedge(y,x,(ld)v);
	}
	for (int i=1;i<=n;i++)
		done[i]=0;
	siz=n;
	root=0;
	ma[0]=inf;
	Getroot(1,0);
	Ans=0.00;
	Work(root,n);
	printf("%.3Lf\n",Ans);
	return 0;
}