【bzoj2559】【IOI2011】【Race】【点分治】

本文主要是介绍【bzoj2559】【IOI2011】【Race】【点分治】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

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

Input

第一行两个整数 n, k
第二..n行每行三个整数表示一条无向边的两端和权值 (注意点的编号从0开始)

Output

一个整数表示最小边数量如果不存在这样的路径输出-1

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

题解：直接上点分治。

对每次计算的子树搞一个f数组,f[i]表示在当前子树中边权为i的路径的最小长度。

然后我们再维护一个dis数组和d数组，分别表示在当前子树中点i到根的权值和和深度。

显然对于当前计算的子树的每个点x,f[dis[x]]=min(f[dis[x]],d[x]);

ans=min(ans,f[k-dis[x]]+d[x]);

在dfs中维护着两个量即可。

注意每次做完一颗子树要再dfs一边把f数组清空。

代码：

#include<iostream>
#include<cstdio>
#define N 200010
using namespace std;
int point[N],n,k,cnt,next[N*2],x,y,s[N],h[N],ans,f[N*10],dis[N],d[N],r,temp,w;
bool visit[N];
struct use{int st,en,v;}e[N*2];
void add(int x,int y,int v){next[++cnt]=point[x];point[x]=cnt;e[cnt].st=x;e[cnt].en=y;e[cnt].v=v;
}
void dfs(int x,int fa){s[x]=1;h[x]=0;for (int i=point[x];i;i=next[i]){if (e[i].en!=fa&&!visit[e[i].en]){dfs(e[i].en,x);s[x]+=s[e[i].en];h[x]=max(h[x],s[e[i].en]);}}h[x]=max(h[x],temp-s[x]);if (h[x]<h[r]) r=x;
}
void calc(int x,int fa){if (dis[x]<=k) ans=min(ans,f[k-dis[x]]+d[x]);for (int i=point[x];i;i=next[i])if (e[i].en!=fa&&!visit[e[i].en]){d[e[i].en]=d[x]+1;dis[e[i].en]=dis[x]+e[i].v;calc(e[i].en,x);}             
}
void updata(int x,int fa,bool p){if(dis[x]<=k){if(p)f[dis[x]]=min(f[dis[x]],d[x]);else f[dis[x]]=99999999;}for(int i=point[x];i;i=next[i])if(e[i].en!=fa&&!visit[e[i].en])updata(e[i].en,x,p);
}
void solve(int x){visit[x]=1;f[0]=0;for (int i=point[x];i;i=next[i]){if (!visit[e[i].en]){d[e[i].en]=1;dis[e[i].en]=e[i].v;calc(e[i].en,0);updata(e[i].en,0,1);}}for (int i=point[x];i;i=next[i])if (!visit[e[i].en]) updata(e[i].en,0,0);for (int i=point[x];i;i=next[i]){if (!visit[e[i].en]){r=0;temp=s[e[i].en];dfs(e[i].en,0);solve(r);}}
}
int main(){scanf("%d%d",&n,&k);for (int i=1;i<n;i++){scanf("%d%d%d",&x,&y,&w);x++;y++;add(x,y,w);add(y,x,w);}for (int i=1;i<=k;i++) f[i]=n;temp=ans=h[0]=n;dfs(1,0);solve(r);if (ans!=n) cout<<ans<<endl;else cout<<"-1"<<endl;
}

这篇关于【bzoj2559】【IOI2011】【Race】【点分治】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！