有關(guān)消防一題中最優(yōu)解一定在直徑上的證明
P2491 [SDOI2011] 消防
P1099 [NOIP2007 提高組] 樹網(wǎng)的核

題目描述

在一顆 \(n\) 個節(jié)點的無根樹中，找到一條不超過 \(s\) 的路徑，使得圖中所有點到此路徑距離的最大值最小，圖中邊權(quán)非負

分析

若想將此題轉(zhuǎn)化到樹網(wǎng)的核，需要證明對于任意一條不在直徑上的路徑，都能在直徑上找到更優(yōu)解
首先理解一個顯然的結(jié)論：路徑越長，結(jié)果越優(yōu)

證明

以下過程中所用符號及其含義:

• \(f(i)\) 表示從 \(i\) 出發(fā)不經(jīng)過直徑上的邊所能到達的最長距離
• \((u, v)\) 為樹的直徑, \(L\) 為直徑長度
• \((A, B)\) 為所取不在直徑上的路徑
• \(d(i, j)\) 為 \(i\) 與 \(j\) 間的路徑長
  
  

Part 1 : 所選路徑與直徑有交集

根據(jù)直徑的最長性，很容易得到如下性質(zhì)：

1. 對于 \((A, C)\) 路徑上的每一點\(i\), 都有\(f(i) \leq d(u, C)\)

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

2. 對于\((D, B)\) 路徑上的每一點 \(i\), 都有\(f(i) \leq d(D, v)\)

通過觀察發(fā)現(xiàn)，只需截取 \((C, D)\) 就能滿足1，2兩條性質(zhì)
由此我們可以將 \((A, C)\) 和 \((D, B)\) 稱作是多余的，完全可以將\(AC, DB\) 的長度轉(zhuǎn)化到直徑上獲得更優(yōu)解


第一部分證畢。

Part 2 : 所選路徑與直徑無交集

\(x \leq y\) ， \(y \geq \dfrac{L} {2}\)

設(shè) \(val1\) 為圖中所有點到 \(AB\) 的最大距離，則一定有

$$val1 = y + z $$

考慮用反證法證明：假設(shè)存在點 \(C\)，使得 \(C\) 到 \(AB\) 的距離大于 \(val1\)

其中 \(C\) 到 \(AB\) 距離的最小值 $$d = val1 + 1$$
為了保證不重不漏，我們也把 \(C\) 到 \(AB\) 的路徑劃分為經(jīng)過直徑與不經(jīng)過直徑兩類

case 1：

$ d + z + y > L $ 矛盾

case 2：

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

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

構(gòu)造更優(yōu)解

考慮在原圖中只取點 \(O\) 作為所選路徑
根據(jù)定義

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

整理一下

第二部分證畢。
由于 \(z\) 可以取到0, 一種更嚴謹?shù)恼f法是：對于任意一條與直徑不相交的路徑都不能在直徑上構(gòu)造出次優(yōu)解

文章來源地址http://www.zghlxwxcb.cn/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;
}

到了這里，關(guān)于從[SDOI2011]消防 到[NOIP2007]樹網(wǎng)的核的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！