[BZOJ2599/Luogu4149][IOI2011]Race(点分治)

发布于 2018-02-26  74 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2599/Luogu4149][IOI2011]Race(点分治)

Description

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

Http

BZOJ
Luogu

Tag

点分治

解决思路

考虑点分治。对于一个重心,我们需要求出一条过重心的合法路径,那么可以考虑开桶,记\(Min[i]\)表示与重心距离\(i\)的经过的边最短的点的编号。那么,接下来的问题是如何不重不漏地找到解。
考虑到我们已经要求这条路径一定要经过当前重心,那么一条合法的路径要么就是直接从重心出发,要么是由两条不同子树的两条路径组合而成的。那么可以考虑计算当前子树答案的时候,先不用它取更新\(Min\)数组,这样可以保证当前答案一定从前面其他子树更新过来,遍历完这一子树后,再把这棵子树的去更新\(Min\)。
需要注意的是,为了保证时间效率高效,每一次初始化\(Min\)不要用\(memset\)。

代码

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

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

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

int n,K,root,nowsum;
ll Ans=inf;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
ll W[maxM],Depth[maxN],Dist[maxN];
int Size[maxN],mxSon[maxN];
bool vis[maxN];
ll Min[maxNum];
int stacktop=0,Stack[maxN];

void Add_Edge(int u,int v,int w);
void GetRoot(int u,int fa);
void Solve(int u);
void GetAns(int u,int dep,int dis,int fa);

int main()
{
    mem(Head,-1);mem(Min,63);
    ios::sync_with_stdio(false);
    cin>>n>>K;
    for (int i=1;i<n;i++)
    {
        int u,v,w;cin>>u>>v>>w;u++;v++;
        Add_Edge(u,v,w);Add_Edge(v,u,w);
    }
    root=0;mxSon[0]=inf;nowsum=n;
    GetRoot(1,0);
    Solve(root);
    if (Ans==inf) printf("-1\n");
    else printf("%lld\n",Ans);
    return 0;
}

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

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

void Solve(int u)//点分治
{
    Min[0]=0;stacktop=0;//注意这里要把Min[0]置为0,因为直接从重心出发的路径也是合法的。
    for (int i=Head[u];i!=-1;i=Next[i])
        if (vis[V[i]]==0)
        {
            int lasttop=stacktop;//把这一次的点先放入栈中
            GetAns(V[i],1,W[i],u);
            for (int i=lasttop+1;i<=stacktop;i++){//再更新Min
                int u=Stack[i];
                if ((Dist[u]<=K)&&(Min[Dist[u]]>Depth[u])) Min[Dist[u]]=Depth[u];
            }
        }
    for (int i=1;i<=stacktop;i++) if (Dist[Stack[i]]<=K) Min[Dist[Stack[i]]]=inf;//重新初始化Min,方便下一次计算
    vis[u]=1;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (vis[V[i]]==0)
        {
            root=0;nowsum=Size[V[i]];
            GetRoot(V[i],0);
            Solve(root);
        }
    return;
}

void GetAns(int u,int dep,int dis,int fa)
{
    Depth[u]=dep;Dist[u]=dis;Stack[++stacktop]=u;
    if (Dist[u]<=K) Ans=min(Ans,dep+Min[K-Dist[u]]);
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((vis[V[i]]==0)&&(V[i]!=fa))
            GetAns(V[i],dep+1,dis+W[i],u);
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2599/Luogu4149][IOI2011]Race(点分治)


HNCJ OIer