首页 > 代码库 > bzoj2599 [IOI2011]Race

bzoj2599 [IOI2011]Race

2024-08-06 18:28:11   224人阅读

Description

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

Input

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

Output

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

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

2
 
第一次写点分治……要讲详细点
把所有可行解分成过当前点和不过当前点两种情况，过当前点的直接处理，不过当前点的就递归到子树做，然后一样分为过当前点和不过当前点……
然后要找个树的重心，就是把无根树建成以x为根的有根树之后，使子树的儿子个数最大值最小的x
对于这题，用t[k]表示当前子树中到根的路径权值和为k的最短边。换而言之就是权值和为k又经过最少边
然后就可以分治搞掉
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971#define N 200010using namespace std;inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}int n,k,cnt,sum,root,ans;struct edge{	int to,next,v;}e[2*N];int head[N];int f[N];int son[N];int vis[N];int dep[N];int dist[N];int t[1000010];inline void ins(int u,int v,int w){	e[++cnt].to=v;	e[cnt].v=w;	e[cnt].next=head[u];	head[u]=cnt;}inline void insert(int u,int v,int w){	ins(u,v,w);	ins(v,u,w);}inline void getroot(int x,int fa){	son[x]=1;f[x]=0;	for (int i=head[x];i;i=e[i].next)	  if (e[i].to!=fa&&!vis[e[i].to])	  {	  	getroot(e[i].to,x);	  	son[x]+=son[e[i].to];	  	f[x]=max(f[x],son[e[i].to]);	  }	f[x]=max(f[x],sum-son[x]);	if (f[x]<f[root])root=x;}inline void dfs(int x,int fa){	if(dist[x]<=k)ans=min(ans,dep[x]+t[k-dist[x]]);	for (int i=head[x];i;i=e[i].next)	  if (fa!=e[i].to&&!vis[e[i].to])	  {	  	dep[e[i].to]=dep[x]+1;	  	dist[e[i].to]=dist[x]+e[i].v;	  	dfs(e[i].to,x);	  }}inline void add(int x,int fa,int opr){	if (dist[x]<=k)	{		if (opr==1)t[dist[x]]=min(t[dist[x]],dep[x]);		else t[dist[x]]=inf;	}	for (int i=head[x];i;i=e[i].next)	  if (e[i].to!=fa&&!vis[e[i].to])	    add(e[i].to,x,opr);}inline void work(int x){	vis[x]=1;t[0]=0;	for (int i=head[x];i;i=e[i].next)	  if (!vis[e[i].to])	  {	  	dep[e[i].to]=1;dist[e[i].to]=e[i].v;	  	dfs(e[i].to,0);	  	add(e[i].to,0,1);	  }	for (int i=head[x];i;i=e[i].next)	  if (!vis[e[i].to])add(e[i].to,0,0);	for (int i=head[x];i;i=e[i].next)	  if (!vis[e[i].to])	  {		root=0;sum=son[e[i].to];		getroot(e[i].to,0);		work(root);	  }}int main(){	n=read();k=read();	for (int i=1;i<=k;i++)t[i]=n;	for(int i=1;i<n;i++)	{		int x=read()+1,y=read()+1,z=read();		insert(x,y,z);	}	ans=sum=f[0]=n;	getroot(1,0);	work(root);	if (ans==n)printf("-1\n");	else printf("%d\n",ans);	return 0;}

　　

bzoj2599 [IOI2011]Race


联系
我们