应该都和我一样一下水了两题吧
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 < val1$$
因此对于每一条与直径不相交的路径都能在直径上构造出更优解
第二部分证毕。
AC代码
#include#include#include#include#define ll long longusing namespace std;const ll N = 5e5 + 5, inf = 0x3f3f3f3f3f3f3f3f;int n, vis[N], a[N];ll s, d[N], sum[N];vector<pair > 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; ++ i) {if(d[ret] > 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 <= 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, max(sum[i], sum[idx] - sum[j])));}cout << ans;return 0;}