[WC2010][BZOJ1758]重建计划-[二分+分数规划+点分治]

Description

传送门

Solution

看到那个式子，显然想到分数规划。。。（不然好难呢）

然后二分答案，则每条边的权值设为g(e)-ans。最后要让路径长度在[L,U]范围内的路径权值>=0

接下来我们就要找路径了。。

考虑树形dp或者分治。

假如是树形dp需要用长链剖分优化。

我的写法是点分治，非常暴力的思路em。就是枚举经过某个点的路径，注意判断长度。mx[i]记录子树内深度为i的点到目前重心的最大权值。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int inf=0x3f3f3f3f;
const double eps=1e-4;
int n,L,U,x,y,v;
struct pas{int y,nxt,real_dis;}g[200010];int h[100010],tot=0;
 
bool vis[100010];
 
int sz[100010],dep[100010],mx_sz[100010],S,rt;
void get_rt(int x,int f)
{
    sz[x]=1;dep[x]=dep[f]+1;mx_sz[x]=0;
    for (int i=h[x];i;i=g[i].nxt)
    if (g[i].y!=f&&!vis[g[i].y])
    {
        get_rt(g[i].y,x),sz[x]+=sz[g[i].y];mx_sz[x]=max(mx_sz[x],sz[g[i].y]);       
    }
    mx_sz[x]=max(mx_sz[x],S-sz[x]);
    if (mx_sz[x]<mx_sz[rt]) rt=x;
}
double dis[100010],mx[100010];
int fa[100010];
int q[100010],dis_q[100010],l,r;
bool check(int x,double d)
{
    int _sz=0,u,v;
    for (int i=h[x];i;i=g[i].nxt)
    {
        fa[g[i].y]=x;
        l=1,r=1;q[1]=g[i].y;dis[g[i].y]=g[i].real_dis-d;dep[g[i].y]=1;
        while (l<=r)
        {
            u=q[l];l++;
            if (dep[u]>U) break;
            for (int t=h[u];t;t=g[t].nxt)
            if (!vis[g[t].y]&&g[t].y!=fa[u])
            {
                v=g[t].y;               
                fa[v]=u;
                dis[v]=dis[u]+g[t].real_dis-d;
                dep[v]=dep[u]+1;
                if (dep[v]>U) break;
                q[++r]=v;
            }
        }
        int re=r,now=_sz;l=1,r=0;
        for (int j=1;j<=re;j++)
        {
            u=q[j];
            while (now>=0&&dep[u]+now>=L)
            {
                while (l<=r&&mx[dis_q[r]]<mx[now]) r--;
                dis_q[++r]=now;now--;
            }
            while (l<=r&&dis_q[l]+dep[u]>U) l++;
            if (l<=r&&dis[u]+mx[dis_q[l]]>=0) return 1;
        }
        for (int t=_sz+1;t<=dep[q[re]];t++) mx[t]=-inf;
        for (int t=1;t<=re;t++) mx[dep[q[t]]]=max(mx[dep[q[t]]],dis[q[t]]);
        _sz=max(_sz,dep[q[re]]);
    }
    return 0;
}
 
double lim_l=1e9,lim_r=0,ans=0;
void solve(int x)
{
    rt=0;get_rt(x,0);vis[rt]=1;
    double l=lim_l>ans?lim_l:ans,r=lim_r,mid;
    while (r-l>eps)
    {
        mid=(l+r)/2;
        if (check(rt,mid)) l=mid;else r=mid;
    }ans=l;
    for (int i=h[rt];i;i=g[i].nxt) 
    if (!vis[g[i].y]&&sz[g[i].y]>=L) 
    {
        S=sz[g[i].y];solve(g[i].y);
    }
}
int main()
{
    scanf("%d%d%d",&n,&L,&U);
    for (int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&v);
        g[++tot]=pas{y,h[x],v};h[x]=tot;
        g[++tot]=pas{x,h[y],v};h[y]=tot;
        lim_l=min(lim_l,(double)v);
        lim_r=max(lim_r,(double)v);
    }
    mx_sz[0]=inf;dep[0]=-1;
    S=n;solve(1);
    printf("%.3f",ans);
}