P4292 [WC2010]重建计划(点分治)
nofind
·
·
个人记录
题意
看见式子显然分数规划，之后变成查询是否存在一条路径权值和大于0，点分治即可。
注意卡常。
code:
```
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const double inf=1e18;
const double eps=1e-4;
int n,m,L,R,cnt_edge,tot;
int head[maxn],a[maxn];
struct edge{int to,nxt;double dis;}e[maxn<<1];
inline int read()
{
char c=getchar();int res=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
return res*f;
}
inline void add_edge(int u,int v,double w)
{
e[++cnt_edge].nxt=head[u];
head[u]=cnt_edge;
e[cnt_edge].to=v;
e[cnt_edge].dis=w;
}
int root,trsize;
int size[maxn],maxs[maxn];
bool vis[maxn];
void getroot(int x,int fa)
{
size[x]=1;maxs[x]=0;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa||vis[y])continue;
getroot(y,x);size[x]+=size[y];
maxs[x]=max(maxs[x],size[y]);
}
maxs[x]=max(maxs[x],trsize-size[x]);
if(maxs[x]<maxs[root])root=x;
}
void init(int x)
{
maxs[root=0]=1e9;trsize=size[x];
getroot(x,0);a[++tot]=root;vis[root]=1;
for(int i=head[root];i;i=e[i].nxt)
{
int y=e[i].to;
if(vis[y])continue;
maxs[root=0]=1e9;trsize=size[y];
getroot(y,x);init(y);
}
}
int now,cnt,last;
int dep[maxn],b[maxn],q[maxn];
double ans;
double f[maxn],dis[maxn];
bool flag;
bool in[maxn];
inline void bfs(int x)
{
in[b[++cnt]=x]=1;
for(int i=last+1;i<=cnt;i++)
{
int y=b[i];
for(int j=head[y];j;j=e[j].nxt)
{
int z=e[j].to;
if(vis[z]||in[z])continue;
dis[z]=dis[y]+e[j].dis;dep[z]=dep[y]+1;
in[b[++cnt]=z]=1;
}
}
for(int i=last+1;i<=cnt;i++)in[b[i]]=0;
}
void solve(int x)
{
vis[x]=1;
f[0]=dis[x]=dep[x]=0;b[cnt=0]=x;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(vis[y])continue;
dis[y]=e[i].dis;dep[y]=1;
last=cnt;bfs(y);
int l=1,r=0;
for(int j=min(R,dep[b[cnt]]),k=last+1;j;j--)
{
while(l<=r&&j+dep[q[l]]<L)l++;
while(k<=cnt&&j+dep[b[k]]<L)k++;
while(k<=cnt&&j+dep[b[k]]<=R)
{
while(l<=r&&dis[q[r]]+eps<=dis[b[k]])r--;
q[++r]=b[k];k++;
}
if(l<=r&&f[j]+dis[q[l]]>=-eps)flag=1;
}
for(int j=last+1;j<=cnt;j++)f[dep[b[j]]]=max(f[dep[b[j]]],dis[b[j]]);
}
for(int i=0;i<=cnt;i++)f[dep[b[i]]]=-inf;
if(flag)return;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(vis[y])continue;
solve(a[++now]);
if(flag)return;
}
}
inline bool check(double mid)
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=cnt_edge;i++)e[i].dis-=mid;
//ans=-inf;
flag=0;solve(a[now=1]);
for(int i=1;i<=cnt_edge;i++)e[i].dis+=mid;
return flag;//ans>=-eps;
}
int main()
{
n=read(),L=read(),R=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read(),w=read();
add_edge(u,v,w);add_edge(v,u,w);
}
size[1]=n;init(1);
for(int i=1;i<=n;i++)f[i]=-inf;
double l=0,r=1e6;
for(int i=1;i<=35;i++)
{
double mid=(l+r)/2.0;
if(check(mid))l=mid;
else r=mid;
}
printf("%.3lf",l);
return 0;
}
```