【BZOJ1999】树网的核

题目大意：题目过长，无法简单描述。。。

题解：

由于树网的核一定是树直径的一段，因此考虑先将直径取出，通过两次 BFS 即可。要求的东西是树上任意一点到这条取出的线段的距离的最大值，发现这个最大值有可能为三个值构成，首先是给定段到树直径的两个端点的距离，其次是树直径外的点到给的给定段的距离的最大值。到直径端点的值和直径外的点到给定段的值都可以 \(O(n)\) 预处理出来，最后采用双指针扫一遍取出的直径序列即可求出答案，总时间复杂度为 \(O(n)\)。

代码如下

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int maxn=5e5+10;

int n,s,d[maxn],pre[maxn],st,ed;

int dia[maxn],cnt,dmax;

bool vis[maxn];

queue<int> q;

struct node{

	int nxt,to,w;

}e[maxn<<1];

int tot=1,head[maxn];

inline void add_edge(int from,int to,int w){

	e[++tot]=node{head[from],to,w},head[from]=tot;

}

int bfs(int start){

	memset(d,0x3f,sizeof(d));

	memset(vis,0,sizeof(vis));

	memset(pre,0,sizeof(pre));

	d[start]=0,vis[start]=1,q.push(start);

	while(q.size()){

		int u=q.front();q.pop();

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to,w=e[i].w;

			if(vis[v])continue;

			d[v]=d[u]+w,pre[v]=u;

			vis[v]=1,q.push(v);

		}

	}

	int mx=0,dst=0;

	for(int i=1;i<=n;i++)if(d[i]>mx)mx=d[i],dst=i;

	return dst;

}

void diameter(){

	st=bfs(1);

	ed=bfs(st);

	int now=ed;

	while(now!=st){

		dia[++cnt]=d[now];

		now=pre[now];

	}

	dia[++cnt]=0;

	reverse(dia+1,dia+cnt+1);

}

void read_and_parse(){

	scanf("%d%d",&n,&s);

	for(int i=1;i<n;i++){

		int x,y,z;

		scanf("%d%d%d",&x,&y,&z);

		add_edge(x,y,z),add_edge(y,x,z);

	}

}

void dfs(int u){

	vis[u]=1;

	dmax=max(dmax,d[u]);

	for(int i=head[u];i;i=e[i].nxt){

		int v=e[i].to,w=e[i].w;

		if(vis[v])continue;

		d[v]=d[u]+w;

		dfs(v);

	}

}

void solve(){

	diameter();

	memset(vis,0,sizeof(vis));

	memset(d,0,sizeof(d));

	for(int i=ed;i;i=pre[i])vis[i]=1;

	for(int i=ed;i;i=pre[i])dfs(i);

	int ans=0x3f3f3f3f;

	for(int l=1,r=1;l<=cnt;l++){

		while(r<=cnt&&dia[r]-dia[l]<=s)++r;

		int ret=max(dia[l]-dia[1],dia[cnt]-dia[r-1]);

		ans=min(ans,max(ret,dmax));

	}

	printf("%d\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【BZOJ1999】树网的核

最新文章

热门文章