洛谷 P4149 [IOI2011]Race 题解【点分治】【贪心】

作者: wjyyy 分类: 图论,点分治,解题报告,贪心 发布时间: 2019-02-12 16:24

点击量:42

点分+贪心的一道好题。

题目描述

给一棵树,每条边有权。求一条简单路径,权值和等于\(K\),且边的数量最小。

输入输出格式

输入格式:

第一行:两个整数 \(n,k\)。

第二至 \(n\) 行:每行三个整数,表示一条无向边的两端和权值 (注意点的编号从 \(0\) 开始)。

输出格式:

一个整数,表示最小边数量。

如果不存在这样的路径,输出 \(-1\)。

输入输出样例

输入样例#1:

4 3
0 1 1
1 2 2
1 3 4

输出样例#1:

2

说明

\(n\le 200000,K\le 1000000\)。

题解

今天刚学了点分,做了几个题,感觉这个最有意思(虽然还是比较裸)。

首先提一下点分的注意事项吧:

  • 找重心时
    • 对一个子联通块中的点,父亲方向的子树大小要用当前子联通块中的总数减去当前点的子树大小,而不是原始的\(n\)。
    • 注意判不等于来源以及不等于已经当过重心的点。
  • 分治时
    • 删除记录数据只用删修改过的(存在栈里),以保证复杂度。
    • 如果无边权,上述操作可以暴力删,因为有数据的桶一定是连续的。
    • rt每次要变为缺省值。
    • 进dfs前要更新这条边的长度到dep上去。
  • dfs时
    • 如果当前dep已经超过\(k\)了,则可以直接返回,子树中都更新不了答案,而且没有需要用到的信息。
    • (针对本题)注意两个dep都要还原现场啊😭。
  • 其他
    • 桶/树状数组要开到\(k\)的规模才可以。如果没有用到上面的剪枝的话甚至要开到\(nw\)的规模。

然后此题的桶\(b[i]\)中存的是长度为\(i\)的到根的路径的最少边条数。当不存在这样的路径时,\(b[i]=\inf\)。

每次更新要比较大小后再存。

然后注意标号从\(0\)开始,无解输出\(-1\)。

这篇题解真水

Code:

#include<stack>
#include<cstdio>
#include<cstring>
using std::stack;
int Min(int x,int y)
{
    return x<y?x:y;
}
struct edge
{
    int n,nxt,v;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[400000];
int head[200100],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],v);
    head[to]=ecnt;
}
int rt,sz[200100],f[200100],n,k;
bool used[200100];
void getroot(int x,int from)
{
    sz[x]=1;
    f[x]=0;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=from&&!used[e[i].n])
        {
            getroot(e[i].n,x);
            sz[x]+=sz[e[i].n];
            f[x]=f[x]>sz[e[i].n]?f[x]:sz[e[i].n];
        }
    f[x]=f[x]>(n-sz[x])?f[x]:(n-sz[x]);
    rt=f[rt]<f[x]?rt:x;
}
stack<int> s1,s2;
int d[200100],D[200100],b[1000100],dep=0,Dep=0,ans=0x3fffffff;
void dfs(int x,int from)
{
    if(dep>k)
        return;
    d[x]=dep;
    D[x]=Dep;
    s1.push(x);
    s2.push(x);
    ans=ans<(Dep+b[k-dep])?ans:(Dep+b[k-dep]);
    ++Dep;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=from&&!used[e[i].n])
        {
            dep+=e[i].v;
            dfs(e[i].n,x);
            dep-=e[i].v;
        }
    --Dep;
}
void divide(int x)
{
    n=sz[x];
    rt=200000;
    getroot(x,x);
    used[rt]=1;
    for(int i=head[rt];~i;i=e[i].nxt)
        if(!used[e[i].n])
        {
            dep=e[i].v;
            Dep=1;
            dfs(e[i].n,rt);
            while(!s1.empty())
            {
                int p=s1.top();
                s1.pop();
                b[d[p]]=Min(b[d[p]],D[p]);
            }
        }
    while(!s2.empty())
    {
        b[d[s2.top()]]=0x3f3f3f3f;
        s2.pop();
    }
    for(int i=head[rt];~i;i=e[i].nxt)
        if(!used[e[i].n])
            divide(e[i].n);
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(b,0x3f,sizeof(b));
    f[200000]=2e9;
    b[0]=0;
    int u,v,w;
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    sz[0]=n;
    divide(0);
    printf("%d\n",ans>0x30000000?-1:ans);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */