从[SDOI2011]消防到[NOIP2007]树网的核-Toy模板网

这篇具有很好参考价值的文章主要介绍了从[SDOI2011]消防到[NOIP2007]树网的核。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

有关消防一题中最优解一定在直径上的证明
P2491 [SDOI2011] 消防
P1099 [NOIP2007 提高组] 树网的核

题目描述

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

分析

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

证明

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

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

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

从[SDOI2011]消防到[NOIP2007]树网的核
根据直径的最长性，很容易得到如下性质：

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

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

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

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

第一部分证毕。

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

从[SDOI2011]消防到[NOIP2007]树网的核

$x \leq y$ ， $y \geq \dfrac{L} {2}$

设 $val1$ 为图中所有点到 $AB$ 的最大距离，则一定有

$$val1 = y + z $$

考虑用反证法证明：假设存在点 $C$，使得 $C$ 到 $AB$ 的距离大于 $val1$

其中 $C$ 到 $AB$ 距离的最小值 $$d = val1 + 1$$
为了保证不重不漏，我们也把 $C$ 到 $AB$ 的路径划分为经过直径与不经过直径两类

case 1：

从[SDOI2011]消防到[NOIP2007]树网的核
$ d + z + y > L $ 矛盾

case 2：

从[SDOI2011]消防到[NOIP2007]树网的核
$(d - w - z) + (x + w) = x + y + 1 > L$ 矛盾

因此 $ val1 = y + z $ 得证。

构造更优解

从[SDOI2011]消防到[NOIP2007]树网的核
考虑在原图中只取点 $O$ 作为所选路径
根据定义

\[val2 = max(x, y, f(O)) = y \]

$f(O) \leq \dfrac{L}{2} $

整理一下

\[va1 = y + z, val2 = y \]

\[val2 \leq val1 \]

第二部分证毕。
由于 $z$ 可以取到0, 一种更严谨的说法是：对于任意一条与直径不相交的路径都不能在直径上构造出次优解

文章来源地址https://www.toymoban.com/news/detail-745972.html

AC代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;
const ll N = 5e5 + 5;

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

vector<pair<int, ll> > H[N];
pair<int, ll> pre[N];

int bfs(int source) {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.push(source);
	d[source] = 0;
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		for(auto [y, z] : H[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; ++ i) {
		if(d[ret] < d[i]) ret = i;
	}
	return ret;
}

void dfs(int x) {
	vis[x] = 1, d[x] = 0;
	for(auto [y, z] : H[x]) {
		if(vis[y]) continue;
		dfs(y);
		d[x] = max(d[x], d[y] + z);
	} 
}

int main() {
	ios :: sync_with_stdio(0);
	cin.tie(nullptr);
	cin >> n >> s;
	for(int i = 1, x, y, z; i < n; ++ i) {
		cin >> x >> y >> z;
		H[x].push_back({y, z});
		H[y].push_back({x, z});
	}
	int u = bfs(1);
	int v = bfs(u);
	int p = v, idx; ll maxd = -2e9, ans = 2e9;
	while(p != u) {
		a[++ idx] = p;
		p = pre[p].first;
	}
	a[++ idx] = u;
	for(int i = 1; i <= idx; ++ i) vis[a[i]] = 1;
	for(int i = 1; i <= idx; ++ i) {
		dfs(a[i]);
		sum[i] = sum[i - 1] + pre[a[i - 1]].second;
		maxd = max(maxd, d[a[i]]);
	}
	for(int i = 1, j = 1; i <= idx; ++ i) {
		while(sum[j + 1] - sum[i] <= s && j < idx) ++ j;
		ans = min(ans, max({maxd, sum[i], sum[idx] - sum[j]}));
	}
	cout << ans;
	return 0;
}

到了这里，关于从[SDOI2011]消防到[NOIP2007]树网的核的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

从[SDOI2011]消防到[NOIP2007]树网的核

题目描述

分析