洛谷P4149 [IOI2011]Race（点分治）

题目描述

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

输入输出格式

输入格式：

第一行：两个整数 n,kn,k 。

第二至 nn 行：每行三个整数，表示一条无向边的两端和权值 (注意点的编号从 00 开始)。

输出格式：

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

如果不存在这样的路径，输出 -1−1 。

输入输出样例

输入样例#1：

输出样例#1：

说明

n\le 200000,K\le 1000000n≤200000,K≤1000000 。

题解：谁说点分一定要套容斥的？

这题的暴力思路大约跟dp有点像，每次爆枚到一棵子树中每一个点的距离，显然对于这些距离di，能与他产生解的是之前所有子树中到达距离为k-di的点的最小深度。

然后就是一遍dfs爆枚所有点，再一遍dfs更新所有最小深度，然后就可以a掉了

代码如下：

#include<map>

#include<set>

#include<queue>

#include<cmath>

#include<cstdio>

#include<string>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define mp make_pair

#define pii pair<int,int>

#define inf 0x3f3f3f3f

using namespace std;

#define int ll

typedef long long ll;

int n,k,deep[],dis[],size[],fa[],vis[];

int tmp[],ans;

vector<pii> g[];

void get_size(int now,int f)

{

    size[now]=;

    fa[now]=f;

    for(int i=; i<g[now].size(); i++)

    {

        if(vis[g[now][i].first]||g[now][i].first==f) continue;

        get_size(g[now][i].first,now);

        size[now]+=size[g[now][i].first];

    }

}

int get_zx(int now,int f)

{

    if(size[now]==) return now;

    int son,maxson=-;

    for(int i=; i<g[now].size(); i++)

    {

        if(vis[g[now][i].first]||g[now][i].first==f) continue;

        if(size[g[now][i].first]>maxson)

        {

            maxson=size[g[now][i].first];

            son=g[now][i].first;

        }

    }

    int zx=get_zx(son,now);

    while(size[zx]<*(size[now]-size[zx])) zx=fa[zx];

    return zx;

}

void calc(int now,int f,int dep,int di)

{

    deep[now]=dep;

    dis[now]=di;

    if(dis[now]<=k) ans=min(ans,tmp[k-dis[now]]+deep[now]);

    else return;

    for(int i=; i<g[now].size(); i++)

    {

        if(vis[g[now][i].first]||g[now][i].first==f) continue;

        calc(g[now][i].first,now,dep+,di+g[now][i].second);

    }

}

void dfs(int now,int f,int kd)

{

    if(kd) tmp[dis[now]]=min(tmp[dis[now]],deep[now]);

    else tmp[dis[now]]=inf;

    for(int i=;i<g[now].size();i++)

    {

        if(vis[g[now][i].first]||g[now][i].first==f) continue;

        dfs(g[now][i].first,now,kd);

    }

}

void solve(int now)

{

    vis[now]=;

    tmp[]=;

    for(int i=;i<g[now].size();i++)

    {

        if(vis[g[now][i].first]) continue;

        calc(g[now][i].first,,,g[now][i].second);

        dfs(g[now][i].first,,);

    }

    for(int i=;i<g[now].size();i++)

    {

        if(vis[g[now][i].first]) continue;

        dfs(g[now][i].first,,);

    }

    for(int i=;i<g[now].size();i++)

    {

        if(vis[g[now][i].first]) continue;

        get_size(g[now][i].first,);

        int zx=get_zx(g[now][i].first,);

        solve(zx);

    }

}

main()

{

    scanf("%lld%lld",&n,&k);

    for(int i=;i<n;i++)

    {

        int from,to,cost;

        scanf("%lld%lld%lld",&from,&to,&cost);

        g[from+].push_back(mp(to+,cost));

        g[to+].push_back(mp(from+,cost));

    }

    ans=inf;

    memset(tmp,0x3f,sizeof(tmp));

    solve();

    ans==0x3f3f3f3f?puts("-1"):printf("%lld\n",ans);

}

巴特西

洛谷P4149 [IOI2011]Race（点分治）

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章