[BZOJ3672/Luogu2305][NOI2014]购票(点分治,动态规划,斜率优化)

发布于 2018-04-08  90 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3672/Luogu2305][NOI2014]购票(点分治,动态规划,斜率优化)

Description

今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发,到SZ市参加这次盛会。
全国的城市构成了一棵以SZ市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v,我们给出了它在这棵树上的父亲城市 fv 以及到父亲城市道路的长度 sv。
从城市 v 前往SZ市的方法为:选择城市 v 的一个祖先 a,支付购票的费用,乘坐交通工具到达 a。再选择城市 a 的一个祖先 b,支付费用并到达 b。以此类推,直至到达SZ市。
对于任意一个城市 v,我们会给出一个交通工具的距离限制 lv。对于城市 v 的祖先 a,只有当它们之间所有道路的总长度不超过 lv 时,从城市 v 才可以通过一次购票到达城市 a,否则不能通过一次购票到达。对于每个城市 v,我们还会给出两个非负整数 pv,qv 作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d,那么从城市 v 到城市 a 购买的票价为 dpv+qv。
每个城市的OIer都希望自己到达SZ市时,用于购票的总资金最少。你的任务就是,告诉每个城市的OIer他们所花的最少资金是多少。

Tag

点分治,动态规划,斜率优化

解决思路

设F[i]表示i这一点到达根的最优值,那么对于每一个合法的j有,其中Depth[i]表示i这一点到根的距离
\[F[i]=min(F[j]+(Depth[i]-Depth[j])*P[i]+Q[i])\]
但关键就是这个合法的j不好确定。就算没有距离的限制,要想在树上动态维护一个凸包?可持久化凸包?再加上个距离的限制,完全不能解。
考虑另一种方法。假设对于一个点i,我们已经能够确定i以及i到根路径上所有的点的答案,那么如何用这些答案取更新i的子树内的点的答案呢?
考虑把i子树内的点按照它的深度-距离限制排序,这样就可以得到一个单调的序列。同时,我们从i开始跳i的父亲,每一次把符合当前限制的点加入凸包,这样我们就可以用i到根路径上的点的权值来更新i子树内的点了。
那么,如何选择这个点i呢?为了保证复杂度,可以用点分治来解决。每一次点分治重心,先递归处理重心到当前真正的根,得到这一条路径上的答案,这样才能用来更新重心的子树。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=200010;
const int maxM=maxN*2;
const int inf=2147483647;

class Data
{
public:
    ll p,q,l;
};

class Edge
{
public:
    int v;ll w;
};

int n;
int edgecnt=0,Head[maxN],Next[maxM];
Edge E[maxM];
int nowsum,root,Size[maxN],mxSon[maxN],Fa[maxN];
ll F[maxN],Dist[maxN];
int qh,Queue[maxN],Stack[maxN];
Data P[maxN];
bool vis[maxN];

void Add_Edge(int u,int v,int w);
void dfs_init(int u,int fa);
void GetRoot(int u,int fa);
void Divide(int u);
bool cmp(int u,int v);
void dfs(int u,int fa);
ld Slope(int u,int v);

int main()
{
    ios::sync_with_stdio(false);mem(Head,-1);mem(F,63);

    cin>>n;int opt;cin>>opt;
    for (int i=2;i<=n;i++)
    {
        ll fa,dis;cin>>fa>>dis>>P[i].p>>P[i].q>>P[i].l;
        Add_Edge(i,fa,dis);Add_Edge(fa,i,dis);
    }
    Dist[1]=0;F[1]=0;
    dfs_init(1,1);
    nowsum=n;root=0;mxSon[0]=inf;
    Divide(1);

    for (int i=2;i<=n;i++) cout<<F[i]<<endl;
    return 0;
}

void Add_Edge(int u,int v,int w)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt].v=v;E[edgecnt].w=w;
    return;
}

void dfs_init(int u,int fa)
{
    Size[u]=1;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (E[i].v!=fa)
        {
            Fa[E[i].v]=u;Dist[E[i].v]=Dist[u]+E[i].w;
            dfs_init(E[i].v,u);
            Size[u]+=Size[E[i].v];
        }
    return;
}

void GetRoot(int u,int fa)//得到重心
{
    Size[u]=1;mxSon[u]=0;
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((E[i].v!=fa)&&(vis[E[i].v]==0))
        {
            GetRoot(E[i].v,u);
            Size[u]+=Size[E[i].v];
            mxSon[u]=max(mxSon[u],Size[E[i].v]);
        }
    mxSon[u]=max(mxSon[u],nowsum-Size[u]);
    if (mxSon[u]<mxSon[root]) root=u;
    return;
}

void Divide(int u)//点分治
{
    if (nowsum<=1) return;
    root=0;GetRoot(u,u);int nowroot=root;//得到当前分治区域的重心

    nowsum=Size[u]-Size[root];vis[root]=1;
    Divide(u);//先分治当前根到重心这一区域

    for (int i=nowroot;i!=Fa[u];i=Fa[i])
        if (P[nowroot].l>=Dist[nowroot]-Dist[i])//用u到重心路径上的答案来更新重心的答案
        {
            F[nowroot]=min(F[nowroot],F[i]+(Dist[nowroot]-Dist[i])*P[nowroot].p+P[nowroot].q);
        }

    qh=0;
    for (int i=Head[nowroot];i!=-1;i=Next[i])//得到当前区域内除原根所在区域的所有点
        if ((vis[E[i].v]==0)&&(E[i].v!=Fa[nowroot])) dfs(E[i].v,nowroot);
    sort(&Queue[1],&Queue[qh+1],cmp);//按照深度-限制进行排序

    int stacktop=0;
    for (int i=1,j=nowroot;i<=qh;i++)
    {
        while ((j!=Fa[u])&&(Dist[j]>=Dist[Queue[i]]-P[Queue[i]].l))//将符合条件的根到重心路径上的点加入凸包
        {
            while ((stacktop>=2)&&(Slope(Stack[stacktop],Stack[stacktop-1])<=Slope(Stack[stacktop],j))) stacktop--;
            Stack[++stacktop]=j;
            j=Fa[j];
        }
        if (stacktop==1)//特判凸包内只有一个点的情况
        {
            if (Dist[Stack[stacktop]]>=Dist[Queue[i]]-P[Queue[i]].l)
                F[Queue[i]]=min(F[Queue[i]],F[Stack[stacktop]]+(Dist[Queue[i]]-Dist[Stack[stacktop]])*P[Queue[i]].p+P[Queue[i]].q);
        }
        else
        {
            int fd=1,l=1,r=stacktop;
            do//二分最优斜率的位置
            {
                int mid=(l+r)>>1;
                if (Slope(Stack[mid],Stack[mid+1])>=P[Queue[i]].p) fd=mid+1,l=mid+1;
                else r=mid-1;
            }
            while (l<=r);
            fd=min(fd,stacktop);//由于若二分到结尾,会多一,所以要与栈顶取min
            if (Dist[Stack[fd]]>=Dist[Queue[i]]-P[Queue[i]].l)
                F[Queue[i]]=min(F[Queue[i]],F[Stack[fd]]+(Dist[Queue[i]]-Dist[Stack[fd]])*P[Queue[i]].p+P[Queue[i]].q);
        }
    }

    for (int i=Head[nowroot];i!=-1;i=Next[i])//点分治子树
        if (vis[E[i].v]==0){
            nowsum=Size[E[i].v];Divide(E[i].v);
        }
    return;
}

void dfs(int u,int fa)
{
    Queue[++qh]=u;
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((E[i].v!=fa)&&(vis[E[i].v]==0)) dfs(E[i].v,u);
    return;
}

bool cmp(int u,int v)
{
    return Dist[u]-P[u].l>Dist[v]-P[v].l;
}

ld Slope(int u,int v)
{
    return 1.0*(F[u]-F[v])/(1.0*(Dist[u]-Dist[v]));
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3672/Luogu2305][NOI2014]购票(点分治,动态规划,斜率优化)


HNCJ OIer 一枚