注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1758 重建计划  

2014-01-16 08:48:10|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题我单个点反正是TLE了……不过bzoj上的总时限把我放过去了
很裸的点分治……
正解是二分+点分治+单调队列,O(n log^2 n)
我是二分+点分治+线段树,O(n log^3 n)
用了个优化是把重心给预处理出来……
但是没用正解那种预处理方法
他是在点分治的时候对子树进行二分,上边界为当前答案。这是一个很厉害的优化,以前省队集训的一个一中的题就要用这个优化

做法很显然就不讲了哈

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
#define maxm 300000
using namespace std;
template<class T>
void Read(T &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
struct Node
{
double max1,max2;
int p1,p2;
Node() {}
Node(double max1,int p1,double max2,int p2): max1(max1),max2(max2),p1(p1),p2(p2) {}
friend Node operator + (Node a,Node b)
{
Node c;
if(a.max1<b.max1)
swap(a,b);
c.p1=a.p1,c.max1=a.max1;
if(a.p1==b.p1)
{
if(a.max2<=b.max2)
c.max2=b.max2,c.p2=b.p2;
else
c.max2=a.max2,c.p2=a.p2;
}
else
{
if(a.max2<=b.max1)
c.max2=b.max1,c.p2=b.p1;
else
c.max2=a.max2,c.p2=a.p2;
}
return c;
}
}Tree[maxm];
int nEdge=1,to[maxm],next[maxm],start[maxn];
double dis[maxm];
int n,L,R,nTree;
int Root[30][maxn];
bool flag[maxn];
void make(int a,int b,double c)
{
++nEdge,to[nEdge]=b,next[nEdge]=start[a],start[a]=nEdge,dis[nEdge]=c;
}
int FindRoot(int p)
{
static int queue[maxn],size[maxn],use[maxn],id,father[maxn];
++id;
int front=0,rear=1;
queue[rear]=p,use[p]=id,size[p]=1,father[p]=0;
while(front<rear)
{
int p=queue[++front];
for(int i=start[p];i;i=next[i])
if(use[to[i]]!=id&&flag[to[i]]==false)
{
use[to[i]]=id,father[to[i]]=p,size[to[i]]=1;
queue[++rear]=to[i];
}
}
for(int i=rear;i>1;--i)
size[father[queue[i]]]+=size[queue[i]];
for(int i=rear;i>=1;--i)
{
int p=queue[i],m=rear-size[p];
for(int j=start[p];j&&m*2<=rear;j=next[j])
if(father[to[j]]==p&&flag[to[j]]==false)
m=max(m,size[to[j]]);
if(m*2<=rear)
return p;
}
}
Node Query(int l,int r)
{
Node ans=Node(-1<<30,0,-1<<30,0);
for(l=l+nTree-1,r=r+nTree+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1)
ans=ans+Tree[l^1];
if(r&1)
ans=ans+Tree[r^1];
}
return ans;
}
void read()
{
Read(n),Read(L),Read(R);
double c;
for(int i=2,a,b;i<=n;++i)
{
Read(a),Read(b),Read(c);
make(a,b,c),make(b,a,c);
}
}
bool work(int p)
{
static Node tmp[maxn];
static double val[maxn];
static int queue[maxn],pos[maxn],use[maxn],id,dep[maxn];
int front=0,rear=0,cnt=0;
use[p]=++id;
for(int i=start[p];i;i=next[i])
if(flag[to[i]]==false)
{
queue[++rear]=to[i],use[to[i]]=id,pos[rear]=++cnt,dep[rear]=1;
val[rear]=dis[i];
}
while(front<rear)
{
int p=queue[++front];
for(int i=start[p];i;i=next[i])
if(flag[to[i]]==false&&use[to[i]]!=id)
{
queue[++rear]=to[i],use[to[i]]=id;
pos[rear]=pos[front],dep[rear]=dep[front]+1,val[rear]=val[front]+dis[i];
}
}
int tot=0;
for(int i=1,j;i<=rear;i=j)
{
tmp[++tot]=Node(-1<<30,0,-1<<30,0);
for(j=i;dep[j]==dep[i]&&j<=rear;++j)
tmp[tot]=tmp[tot]+Node(val[j],pos[j],-1<<30,0);
if(tot>=L&&tot<=R&&tmp[tot].max1>=0)
return true;
}
if(tot*2<L)
return false;
for(nTree=1;nTree-2<tot;nTree<<=1);
for(int i=nTree+1;i<=nTree+tot;++i)
Tree[i]=tmp[i-nTree];
for(int i=nTree+rear+1;i<=nTree+nTree;++i)
Tree[i]=Node(-1<<30,0,-1<<30,0);
for(int i=nTree;i>=1;--i)
Tree[i]=Tree[i<<1]+Tree[i<<1|1];
for(int i=max(1,L-tot);i<=tot&&i*2+1<=R;++i)
{
Node a=tmp[i],b=Query(max(1,L-i),min(R-i,tot));
if(a.p1!=b.p1)
{
if(a.max1+b.max1>=0)
return true;
else
continue;
}
if(a.max1+b.max2>=0)
return true;
if(a.max2+b.max1>=0)
return true;
}
return false;
}
void Prepare(int dep,int p)
{
Root[dep][p]=FindRoot(p),p=Root[dep][p];
flag[p]=true;
for(int i=start[p];i;i=next[i])
if(flag[to[i]]==false)
Prepare(dep+1,to[i]);
}
bool DFS(int dep,int p)
{
p=Root[dep][p];
bool can=work(p);
if(can)
return true;
flag[p]=true;
for(int i=start[p];i;i=next[i])
if(flag[to[i]]==false&&DFS(dep+1,to[i]))
return true;
return false;
}
bool check(double v)
{
for(int i=1;i<=n;++i)
flag[i]=false;
for(int i=2;i<=nEdge;++i)
dis[i]-=v;
bool mark=DFS(1,1);
for(int i=2;i<=nEdge;++i)
dis[i]+=v;
return mark;
}
double binary(double l,double r)
{
while(r-l>1e-5)
{
double mid=(l+r)/2;
check(mid)?l=mid:r=mid;
}
return l;
}
int main()
{
read();
Prepare(1,1);
printf("%.3f\n",binary(1,1000000));
return 0;
}

  评论这张
 
阅读(500)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017