bzoj-2599 Race

题意：
给出一棵n个点的树，每条边有一个权值；
求一条路径，权值和等于K，且边的数量最小；
n<=200000，K<=1000000；

题解：
没数据范围的坑爹题；
此题O(nlog^2n)是过不了的，要O(nlogn)的算法；
注意K的范围！

首先将树分治，答案一定在过根的某条链上；
那么统计子树之间的长度加和为K的链经过的边数；
因为K较小所以直接开一个数组记录长度为x的链最小经过了多少条边就可以了；
同样不能清数组，开个栈记录一下修改位置然后清掉；
因为每一层都是线性的所以时间复杂度O(nlogn)；
树分治这东西真是太容易写挂了。。。

代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 210000
#define pr pair<int,int>
using namespace std;
int next[N<<1],to[N<<1],val[N<<1],head[N],ce;
pr st[N];
int hash[1000100],K,ans,top;
bool ban[N];
void add(int x,int y,int v)
{
	to[++ce]=y;
	val[ce]=v;
	next[ce]=head[x];
	head[x]=ce;
}
int getS(int x,int pre)
{
	int size=1,i;
	for(i=head[x];i;i=next[i])
	{
		if(to[i]!=pre&&!ban[to[i]])
		{
			size+=getS(to[i],x);
		}
	}
	return size;
}
int getG(int x,int pre,int tot,int &g)
{
	int size=1,temp,i;
	bool flag=1;
	for(i=head[x];i;i=next[i])
	{
		if(to[i]!=pre&&!ban[to[i]])
		{
			temp=getG(to[i],x,tot,g);
			size+=temp;
			if(temp>(tot>>1))
				flag=0;
		}
	}
	if(tot-size>(tot>>1))
		flag=0;
	if(flag)
		g=x;
	return size;
}
void getP(int x,int pre,int dis,int cnt)
{
	st[++top]=pr(dis,cnt);
	for(int i=head[x];i;i=next[i])
	{
		if(to[i]!=pre&&!ban[to[i]])
		{
			getP(to[i],x,dis+val[i],cnt+1);
		}
	}
}
void calc(int x)
{
	int temp,i,j;
	top=hash[0]=0;
	for(i=head[x];i;i=next[i])
	{
		if(!ban[to[i]])
		{
			temp=top;
			getP(to[i],0,val[i],1);
			for(j=temp+1;j<=top;j++)
				if(st[j].first<=K)
					ans=min(ans,hash[K-st[j].first]+st[j].second);
			for(j=temp+1;j<=top;j++)
				if(st[j].first<=K)
					hash[st[j].first]=min(hash[st[j].first],st[j].second);
		}
	}
	for(i=1;i<=top;i++)
		if(st[i].first<=K)
			hash[st[i].first]=0x3f3f3f3f;
}
void slove(int x,int tot)
{
	ban[x]=1;
	if(tot==1)	return ;
	calc(x);
	int g,i,s;
	for(i=head[x];i;i=next[i])
	{
		if(!ban[to[i]])
		{
			s=getS(to[i],0);
			getG(to[i],0,s,g);
			slove(g,s);
		}
	}
}
int main()
{
	int n,m,i,j,x,y,v;
	scanf("%d%d",&n,&K);
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&v);
		x++,y++;
		add(x,y,v),add(y,x,v);
	}
	memset(hash,0x3f,sizeof(hash));
	getG(1,0,n,x);
	ans=0x3f3f3f3f;
	slove(x,n);
	if(ans==0x3f3f3f3f)	ans=-1;
	printf("%dn",ans);
	return 0;
}

最后

以上就是可耐蛋挞为你收集整理的bzoj-2599 Race的全部内容，希望文章能够帮你解决bzoj-2599 Race所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。