NKOJ 2650 （SDOI 2011） 消防（树的直径+DP+单调队列/二分答案）

发表于 |
字数统计: 1,467字 | 阅读时长 ≈ 6min

P2650【SDOI2011 第2轮 DAY1】消防

问题描述

　　某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi<=1000)。
　　这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。
　　现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。
　　你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。

输入格式

输入包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。

输出格式

　　　输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。

【样例输入1】

5 2
1 2 5
2 3 2
2 4 4
2 5 3

【样例输入2】

8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3

【样例输出1】

5

【样例输出2】

5

【数据规模和约定】

对于20%的数据，n<=300。
对于50%的数据，n<=3000。
对于100%的数据，n<=300000，边长小等于1000。

首先我们需要发现，这条路径必然是建在树的直径上。
至于证明，只需要假设路径Q不在直径上，那么假设距离最远的点不在直径上，易证不可能，因此距离这条路径Q最远的点一定在直径上。
之后再假设一个A点是不在直径上的一个点，我们假设直径上有一条路径P，如果A到P的距离大于了直径的端点到Q的距离，显然是矛盾的，因此任意的A点到P的距离一定小于直径端点到Q的距离，因此得证。

既然如此，我们将直径上的边权设为0，跑一遍BFS，即可求出其他所有点到直径的距离dis，之后我们需要考虑这条路径的位置。

现在，我们只需要在直径上求出一条不超过S的路径使得其他点到他的距离最小，显然这个最小距离不会大于我们之前求出的dis的最大值。

考虑在直径左右两边截掉一部分长度，可以发现，其他点到这条路径的距离如果变大了，那么新的距离不会超过截掉的长度，否则就与直径矛盾。

所以截掉一段后的发生变化的距离中的最大距离必然是直径的左端点或右端点到路径的距离，因此我们只需要求出需要截掉的最短的长度，当然，这个长度是左边和右边分别截掉长度的最大值。

有了上述结论，我们就求出了直径外的点到路径的距离，和直径上的点到路径的最大距离的最小值，取一个max即可。

至于如何求出截掉部分的长度的最小值，可以二分截掉的长度，也可以直接用dp+单调队列维护。

具体可以参考代码

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<deque>
#define N 333333
#define M 666666
using namespace std;
deque<int>Q;
int n,s,S,T,D[N],SS[N],dis[N],cnt,Max,Maxp,ans,Ans=1e9;
int TOT=1,LA[N],NE[M],EN[M],LE[M];
void ADD(int x,int y,int z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void FD(int x,int f,int tot)//找到直径的端点
{
	int i,y;
	if(tot>Max)Max=tot,Maxp=x;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y!=f)FD(y,x,tot+LE[i]);
	}
}
bool FW(int x,int y,int f)//标记直径上的边
{
	int i,u;
	if(x==y)return 1;
	for(i=LA[x];i;i=NE[i])
	{
		u=EN[i];
		if(u==f)continue;
		if(FW(u,y,x))
		{
			D[++cnt]=LE[i];
			LE[i]=LE[i^1]=0;
			return 1;
		}
	}
	return 0;
}
void DFS(int x,int f,int tot)//算出其他点到直径的距离
{
	int i,y;
	dis[x]=tot;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y!=f)DFS(y,x,tot+LE[i]);
	}
}
int main()
{
	int i,x,y,z;
	scanf("%d%d",&n,&s);
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		ADD(x,y,z);ADD(y,x,z);
	}
	Max=Maxp=-1;FD(1,0,0);S=Maxp;//找直径的端点
	Max=Maxp=-1;FD(S,0,0);T=Maxp;//找直径的端点
	FW(S,T,0);DFS(S,0,0);//标记直径+求距离
	for(i=1;i<=n;i++)ans=max(ans,dis[i]);//取最大距离
	for(i=1;i<=cnt;i++)SS[i]=D[i]+SS[i-1];//前缀和，准备dp
	Q.push_back(0);
	for(i=1;i<=cnt;i++)
	{
	    Q.push_back(i);
		while(Q.size()&&SS[i]-SS[Q.front()]>s)Q.pop_front();
		if(Q.size())Ans=min(Ans,max(SS[Q.front()],SS[cnt]-SS[i]));
	}
	printf("%d",max(ans,Ans));
}