M_sea

洛谷4149 [IOI2011]Race
Luogu分析点分治。考虑如果没有“边数最小”这个条件是怎么做的。开一个桶表示某种 $dis$ 是否存在即可。现在...
扫描右侧二维码阅读全文
05
2019/04

洛谷4149 [IOI2011]Race

Luogu

分析

点分治。

考虑如果没有“边数最小”这个条件是怎么做的。开一个桶表示某种 $dis$ 是否存在即可。

现在有了这个条件的话,桶记录一下最小边数即可。

特别注意点从 $0$ 开始(我被坑了好久)。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

struct Edge { int v,w,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

int n,K,root,sumsz,minsz,ans=2e9;
int vis[N],sz[N];
int sta[N],top=0;
int rub[N],rubtop=0;
int dep[N],dis[N];
int o[12000000];

inline void getroot(int u,int fa) {
    sz[u]=1; int now=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (vis[v]||v==fa) continue;
        getroot(v,u),now=max(now,sz[v]),sz[u]+=sz[v];
    }
    now=max(now,sumsz-sz[u]);
    if (now<minsz) root=u,minsz=now;
}

inline void getdep(int u,int fa,int dis_,int dep_) {
    if (dis_>K) return;
    sta[++top]=rub[++rubtop]=u;
    dis[u]=dis_,dep[u]=dep_;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (vis[v]||v==fa) continue;
        getdep(v,u,dis_+e[i].w,dep_+1);
    }
}

inline void calc(int u,int fa,int w) {
    top=0,getdep(u,fa,w,1);
    for (re int i=1;i<=top;++i) {
        int now=sta[i],nowd=dis[now];
        if (!o[K-nowd]) continue;
        ans=min(ans,dep[now]+o[K-nowd]);
    }
    for (re int i=1;i<=top;++i) {
        int now=sta[i],nowd=dis[now];
        if (!o[nowd]) o[nowd]=dep[now];
        else o[nowd]=min(o[nowd],dep[now]);
    }
}


inline void solve(int u) {
    vis[u]=1; rubtop=0;
    for (re int i=head[u];i;i=e[i].nxt)
        if (!vis[e[i].v]) calc(e[i].v,u,e[i].w);
    if (o[K]) ans=min(ans,o[K]);
    for (re int i=1;i<=rubtop;++i) o[dis[rub[i]]]=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (vis[v]) continue;
        sumsz=sz[v],minsz=n,getroot(v,u);
        solve(root);
    }
}

int main() {
    n=read(),K=read();
    for (re int i=1;i<n;++i) {
        int u=read()+1,v=read()+1,w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    sumsz=minsz=n,getroot(1,0);
    solve(root);
    if (ans==2e9) puts("-1");
    else printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 36 PM

发表评论