BZOJ2599 [IOI2011]Race

题目描述

传送门好像权限题。。。。

传送门

题目分析

思考一下这个题想让你干什么，无非是一个限制和一个最优求解问题。

经过谨慎思考，发现这个\(k\)好像很小啊，好像开数组就开的下。。。

考虑直接开数组暴力记录。

然后就可以点分治，开个数组\(tmp\)暴力记录当权是\(dis\)时，最近的距离是多少。明显\(ans=min(ans,tmp[k-dis]+当前距离)\)。这些都可以递归求出来，然后对当前根计算完毕之后，要将\(tmp\)初始化。

是代码呢

#include <bits/stdc++.h>
using namespace std;
#define min(a,b) (a<b?a:b)
const int MAXN=2e5+7;
const int inf=1e9+7;
int size[MAXN],wson[MAXN],root,tmp[MAXN<<3],ans=inf,vis[MAXN],sum,k,n;
int head[MAXN],num;
struct po{
    int nxt,to,dis;
}edge[MAXN<<1];
inline void add_edge(int from,int to,int dis)
{
    edge[++num].nxt=head[from];
    edge[num].to=to;
    edge[num].dis=dis;
    head[from]=num;
}
inline void get_root(int u,int fa)
{
    size[u]=1;wson[u]=0;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(vis[v]||v==fa) continue;
        get_root(v,u);
        size[u]+=size[v];
        if(wson[u]<size[v]) wson[u]=size[v];
    }
    if(sum-size[u]>wson[u]) wson[u]=sum-size[u];
    if(wson[u]<wson[root]) root=u;
}
inline void get_ans(int u,int fa,int dis,int cnt)
{
    if(dis>k) return;
    ans=min(ans,tmp[k-dis]+cnt);
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(!vis[v]&&v!=fa) get_ans(v,u,dis+edge[i].dis,cnt+1);
    }
}
inline void update(int u,int fa,int dis,int cnt)
{
    if(dis>k) return;
    tmp[dis]=min(tmp[dis],cnt);
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(!vis[v]&&v!=fa) update(v,u,dis+edge[i].dis,cnt+1);
    }
}
inline void clear(int u,int fa,int dis){
    if(dis>k) return;
    tmp[dis]=inf;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(!vis[v]&&v!=fa) clear(v,u,dis+edge[i].dis);
    }
}
inline void work(int u)
{
    tmp[0]=0;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(vis[v]) continue;
        get_ans(v,u,edge[i].dis,1);
        update(v,u,edge[i].dis,1);
    }
    clear(u,0,0);
}
inline void solve(int u)
{
    vis[u]=1;work(u);
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(vis[v]) continue;
        sum=size[v];
        root=0;get_root(v,0);solve(root);
    }
}
inline int read()
{
    int x=0,c=1;
    char ch=' ';
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    while(ch=='-')c*=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*c;
}
int main()
{
    n=read();k=read();
    for(int i=1;i<=k;i++) tmp[i]=inf;
    for(int i=1;i<n;i++){
        int x=read()+1,y=read()+1,l=read();
        add_edge(x,y,l);add_edge(y,x,l);
    }
    wson[0]=inf;sum=n;
    get_root(1,0);solve(root);
    printf("%d\n", ans==inf?-1:ans);
}

BZOJ2599 [IOI2011]Race

原文：https://www.cnblogs.com/victorique/p/10292925.html