欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

P4149-[IOI2011]Race【点分治】

程序员文章站 2022-06-15 23:12:02
正题题目链接:https://www.luogu.com.cn/problem/P4149题目大意nnn个点的一棵树,求一条边最少的权值和为kkk的路径。解题思路直接点分治,然后用mapmapmap记录每个权值和的最小边数转移即可。时间复杂度O(nlog⁡2n)O(n\log^2 n)O(nlog2n)codecodecode#include#include#include#include...

正题

题目链接:https://www.luogu.com.cn/problem/P4149


题目大意

n n n个点的一棵树,求一条边最少的权值和为 k k k的路径。


解题思路

直接点分治,然后用 m a p map map记录每个权值和的最小边数转移即可。
时间复杂度 O ( n log ⁡ 2 n ) O(n\log^2 n) O(nlog2n)


c o d e code code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N=2e5+10;
struct node{
	int to,next,w;
}a[N*2];
int n,k,ls[N],f[N],siz[N],sum,root,ans,tot;
bool v[N];
map<int,int> mp;
void groot(int x,int fa){
	if(v[x])return;
	siz[x]=1;f[x]=0;
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(y==fa||v[y])continue;
		groot(y,x);siz[x]+=siz[y];
		f[x]=max(f[x],siz[y]);
	}
	f[x]=max(f[x],sum-siz[x]);
	if(f[x]<f[root])root=x;
}
void ret(int x,int fa,int dep,int w){
	if(v[x])return;
	if(w>=k)return;
	if(mp.count(k-w))ans=min(ans,mp[k-w]+dep);
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(y==fa||v[y])continue;
		ret(y,x,dep+1,w+a[i].w);
	}
	return;
}
void dfs(int x,int fa,int dep,int w){
	if(v[x])return;
	if(dep>ans||w>k)return;
	if(w==k){ans=min(ans,dep);return;}
	if(!mp.count(w))mp[w]=dep;
	else mp[w]=min(mp[w],dep);
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(y==fa||v[y])continue;
		dfs(y,x,dep+1,w+a[i].w);
	}
	return;
}
void calc(int x){
	mp.clear(); 
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		ret(y,x,1,a[i].w);
		dfs(y,x,1,a[i].w);
	}
	return;
}
void solve(int x){
	v[x]=1;calc(x);
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;sum=siz[y];root=n;
		groot(y,x);solve(root);
	}
}
void addl(int x,int y,int w){
	a[++tot].to=y;
	a[tot].next=ls[x];
	ls[x]=tot;a[tot].w=w;
	return;
}
int main()
{
	scanf("%d%d",&n,&k);
	ans=2147483647; 
	for(int i=1;i<n;i++){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		addl(x,y,w);addl(y,x,w);
	}
	sum=root=n;f[n]=2147483647;
	groot(0,0);
	solve(root);
	if(ans==2147483647)printf("-1");
	else printf("%d",ans);
}

本文地址:https://blog.csdn.net/Mr_wuyongcong/article/details/109277723