[LUOGU] 4149 [IOI2011]Race
2024-09-08 08:33:54
点分治裸题
#include<iostream>
#include<cstring>
#include<cstdio> using namespace std; inline int rd(){
int ret=,f=;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-:;
while(isdigit(c))ret=ret*+c-'',c=getchar();
return ret*f;
} const int MAXN=; struct Edge{
int next,to,w;
}e[MAXN<<];
int ecnt,head[MAXN];
inline void add(int x,int y,int w){
e[++ecnt].next = head[x];
e[ecnt].to = y;
e[ecnt].w = w;
head[x] = ecnt;
} int n,m; bool vis[MAXN];
int siz[MAXN];
void getsiz(int x,int pre){
siz[x]=;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(v==pre||vis[v]) continue;
getsiz(v,x);
siz[x]+=siz[v];
}
}
int mn,root;
void getroot(int x,int pre,int tot){
int mx=;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(v==pre||vis[v]) continue;
mx=max(mx,siz[v]);
getroot(v,x,tot);
}
mx=max(mx,tot-siz[x]);
if(mx<mn) mn=mx,root=x;
} int s[MAXN],l[MAXN],sav[MAXN];
int f[],g[];
void dfs(int x,int pre,int dis,int len){
s[++s[]]=dis;l[++l[]]=len;sav[++sav[]]=dis;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(vis[v]||v==pre) continue;
dfs(v,x,dis+e[i].w,len+);
}
} int ans=0x3f3f3f3f;
void dac(int x){
g[]=;f[]=;sav[]=;mn=n;
getsiz(x,-);
getroot(x,-,siz[x]);
int u=root;vis[u]=;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v]) continue;
l[]=;s[]=;dfs(v,x,e[i].w,);
for(int j=s[];j>=;j--){
if(s[j]>m) continue;
if(f[m-s[j]]) ans=min(ans,g[m-s[j]]+l[j]);
}
for(int j=s[];j>=;j--){
if(s[j]>m) continue;//%%%%Monster_Qi
f[s[j]]=;
g[s[j]]=min(g[s[j]],l[j]);
}
}
for(int i=sav[];i>=;i--) if(sav[i]<=m) f[sav[i]]=,g[sav[i]]=0x3f3f3f3f;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!vis[v]) dac(v);
}
} int main(){
memset(g,0x3f,sizeof(g));
n=rd();m=rd();
int x,y,w;
for(int i=;i<n;i++){
x=rd();y=rd();w=rd();
add(x,y,w);add(y,x,w);
}
dac();
if(ans>=0x3f3f3f3f) cout<<-;
else cout<<ans;
return ;
}
最新文章
- ubuntu14.04下安装node.js
- bzoj4025 二分图
- 十三. JEB破解三
- freecodecamp记录
- linux如何编译安装新内核支持NTFS文件系统?(以redhat7.2x64为例)
- XE8 for iOS 状态栏的几种效果
- AjaxFormSubmit使用demo
- KMP算法的Next数组详解
- ProcDump
- HDU 4160
- POJ 3045
- 无需安装Mono的Jexus
- java入门学习笔记之2(Java中的字符串操作)
- github 管理代码: code.Aliyun
- CentOS 7 环境下GitLab安装及基本配置
- C++——list中erase和remove的区别
- Canvas入门到高级详解(中)
- s21day10 python笔记
- 基于IOS上MDM技术相关资料整理及汇总
- python学习疑问