从[SDOI2011]消防到[NOIP2007]树网的核 - 机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询

~~应该都和我一样一下水了两题吧~~
P2491 [SDOI2011] 消防
P1099 [NOIP2007 提高组] 树网的核

题目描述

在一颗 (n) 个节点的无根树中，找到一条不超过 (s) 的路径，使得图中所有点到此路径距离的最大值最小，图中边权非负

分析

若想将此题转化到树网的核，首先要证明对于任意一条不在直径上的路径，都能在直径上找到更优解
首先理解一个显然的结论：路径越长，结果越优

证明

以下过程中所用符号及其含义:

(f(i)) 表示从 (i) 出发不经过直径上的边所能到达的最长距离
((u, v)) 为树的直径, (L) 为直径长度
((A, B)) 为所取不在直径上的路径
(d(i, j)) 为 (i) 与 (j) 间的路径长

Part 1 : 所选路径与直径有交集

根据直径的最长性，很容易得到如下性质：

对于 ((u, C)) 路径上的每一点(i), 都有(f(i) leq d(u, C))

如果大于，那么 $ f(i) + d(i, v) > L$, 与直径的最长性矛盾

对于((D, v)) 路径上的每一点 (i), 都有(f(i) leq d(D, v))

通过观察发现，只需截取 ((C, D)) 就能满足1，2两条性质
由此我们可以将 ((A, C)) 和 ((D, B)) 称作是多余的，完全可以将(AC, DB) 的长度转化到直径上获得更优解

第一部分证毕。

Part 2 : 所选路径与直径无交集

图中边权满足(x leq y)

设 (val1) 为图中所有点到 (AB) 的最大距离，则一定有$$val1 = y + z geq dfrac{L} {2} + 1$$
考虑用反证法证明：假设存在点 (C)，使得 (C) 到 (AB) 的距离大于 (val1)

其中 (C) 到 (AB) 距离的最小值 (d = val1 + 1)

case 1：

$ d + z + y > L $ 矛盾

case 2：

((d – w – z) + (x + w) = x + y + 1 > L) 矛盾

我们可以得到 (val1_min = dfrac{L}{2} + 1)

然后再考虑在原图直径上截一段(PQ leq s)

其中 (a, b leq dfrac{L}{2}), 且对于任意直径上的点 (i) 有 (f(i) leq dfrac{L}{2})

显然有 $$val2 leq dfrac{L}{2} $$ $$ val2
因此对于每一条与直径不相交的路径都能在直径上构造出更优解

第二部分证毕。

AC代码

#include
#include
#include
#include
#define ll long long

using namespace std;
const ll N = 5e5 + 5, inf = 0x3f3f3f3f3f3f3f3f;

int n, vis[N], a[N];
ll s, d[N], sum[N];

vector > son[N];
pair pre[N];

int bfs(int source) {
	memset(d, -1, sizeof d);
	queue q;
	q.push(source);
	d[source] = 0;
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		for(auto [y, z] : son[x]) {
			if(d[y] == -1) {
				d[y] = d[x] + z;
				pre[y] = {x, z};
				q.push(y);
			}
		}
	}
	int ret = source;
	for(int i = 1; i > n >> s;
	for(int i = 1, x, y, z; i > x >> y >> z;
		son[x].push_back({y, z});
		son[y].push_back({x, z});
	}
	int u = bfs(1);
	int v = bfs(u);
	int p = v, idx; ll maxd = -inf, ans = inf;
	while(p != u) {
		a[++ idx] = p;
		p = pre[p].first;
	}
	a[++ idx] = u;
	for(int i = 1; i

机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net