卑微求条T_T
查看原帖
卑微求条T_T
663949
HYLW楼主2024/7/13 17:35
#include<bits/stdc++.h>
using namespace std;
const int N = 310;
int n,k;
int h[N],e[N*2],len[N*2],ne[N*2],idx;
void add(int a,int b,int c){
	e[idx]=b,len[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int ans=0x3f3f3f3f;

int d[N],he[N];
bool s[N];
int dis;
int l[N];
int bfs(int st){
	memset(s,false,sizeof s);
	memset(he,-1,sizeof he);
	queue<int> q;
	q.push(st);
	s[st]=true;
	d[st]=0,he[st]=-1;
	
	int res,p;
	while(q.size()){
		int u=q.front();
		q.pop();
		s[u]=true;
		for(int i=h[u],v;~i;i=ne[i]){
			v=e[i];
			if(s[v])	continue;
			d[v]=d[u]+len[i],he[v]=u;
			if(res<d[v])	res=d[v],p=v;
			if(!s[v])	q.push(v);
		}
	}
	dis=res;
	return p;
}

void bfss(){
	int p=bfs(1+n>>1);
//	printf("	%d %d\n",p,dis);
	int q=bfs(p);
//	printf("	%d %d\n",q,dis);
	
	memset(s,false,sizeof s);
	int sum=0;
	vector<int> ro;
	ro.push_back(10);
	for(int i=q;~i;i=he[i]){
		s[i]=true;
		for(int j=h[i];~j;j=ne[j])
			if(e[j]==he[i]){
				sum+=len[j];
				ro.push_back(j);
				break;
			}
	}
	
	int mad=-1;
	for(int i=q;~i;i=he[i]){
		queue<int> q;
		q.push(i);
		d[i]=0;
		while(q.size()){
			int u=q.front();
			q.pop();
			s[u]=true;
			for(int j=h[u];~j;j=ne[j]){
				int v=e[j];
				if(s[v])	continue;
				d[v]=d[u]+len[j];
				if(l[i]<d[v])	l[i]=d[v];
				if(!s[v])	q.push(v);
			}
		}
		mad=max(mad,l[i]);
//		printf("%d %d\n",i,l[i]);
	}
	
//	printf("-----------\n");
	int su=len[ro[1]],ri=sum-len[ro[1]],a=1,b=1;
	for(int i=q;~i;i=he[i]){
		while(su>k)	su-=len[ro[a]],a++;		
		ans=min(ans,max(mad,max(sum-su-ri,ri)));
//		printf("%d (%d)%d %d\n",mad,su, sum-su-ri,ri);
		b++;
		su+=len[ro[b]],ri-=len[ro[b]];
	}
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<=n+5;i++)	h[i]=-1;
	for(int i=1,u,v,w;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w),add(v,u,w);
	}
	bfss();
	printf("%d",ans);
	return 0;
}
2024/7/13 17:35
加载中...