SDOI2011 消防

wjh15101051's space

卧薪尝胆，厚积薄发。

SDOI2011 消防

Date: Sun Sep 23 21:26:02 CST 2018

In Category: NoCategory

Description：

给一棵树，树边有边权，选一条长度不超过 $m$ 的路径使得所有点到这条路径距离的最大值最小。

$1\leqslant n \leqslant300000$

Solution：

首先有一个性质，就是最后选出来的这条路经一定在直径上，而且是随便一条直径。证明也不难，画个图就会发现如果路径的端点最终离开了直径，那么直径的端点到这条路径的距离一定会增大，且大于把端点放在直径上时的值。

知道这个这题就很好解了，先随便求出一个直径，把他放在序列上，然后把每个点的子树的最大深度放到这个点上，距离不超过 $m$ 可以双指针搞，区间最值可以单调队列搞，和两端点的距离取个最大值更新答案即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m;

#define MAXN 300010

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int d[MAXN];

bool vis[MAXN];

int fa[MAXN],val[MAXN];

inline int bfs(int s)

{

	queue<int> q;q.push(s);

	memset(vis,false,sizeof(vis));

	d[s] = 0;vis[s] = true;fa[s] = 0;

	while(!q.empty())

	{

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

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(!vis[e[i].to])

			{

				fa[e[i].to] = k;val[e[i].to] = e[i].v;

				d[e[i].to] = d[k] + e[i].v;

				vis[e[i].to] = true;

				q.push(e[i].to);

			}

		}

	}

	int ans = s;

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

	{

		if(d[i] > d[ans])ans = i;

	}

	return ans;

}

int s[MAXN],top = 0;

int dep[MAXN];

void getdep(int t,int k,int depth)

{

	dep[t] = max(dep[t],depth);

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		getdep(t,e[i].to,depth + e[i].v);

	}

	return;

}

int sum[MAXN];

int main()

{

	n = read();m = read();

	int a,b,c;

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

	{

		a = read();b = read();c = read();

		add(a,b,c);

	}

	int pos = bfs(1);

	pos = bfs(pos);

	memset(vis,false,sizeof(vis));

	for(int i = pos;i != 0;i = fa[i])

	{

		s[++top] = i;sum[top + 1] = sum[top] + val[i];

		vis[i] = true;

	}

	for(int i = 1;i <= top;++i)getdep(i,s[i],0);

	deque<int> q;

	int ans = 0x3f3f3f3f;

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

	{

		while(sum[r] - sum[l] > m)++l;

		while(!q.empty() && q.front() < l)q.pop_front();

		while(!q.empty() && dep[q.back()] < dep[r])q.pop_back();

		q.push_back(r);

		ans = min(ans,max(dep[q.front()],max(sum[l],sum[top] - sum[r])));//cout << l << " " << r << " " << dep[q.front()] << " " << sum[l] << " " << sum[top] - sum[r] << endl;

	}

	cout << ans << endl;

	return 0;

}

In tag: 树-树的直径技巧-双指针数据结构-单调队列

wjh15101051