P10838 『FLA - I』庭中有奇树
前言
本题解较为基础,推导如何得出二分解题思路。
题目大意
给出无根带权树,双方采取最佳策略,求节点S->T的最短路。
有两种操作:
- 我方至多可以使用一次传送,花费k元从a传送到b(ab不能相邻)。
- 敌方至多可以把m条道路的传送消耗设置为1e9元(单向设置,如设置a->b消耗不影响b->a)。
思路
显然的,答案可以分两种情况。
不使用传送
对方的操作不用看,答案直接S->T的最短路。
使用传送
设传送起点为u,传送终点为v。总体流程为S->u然后传送到v然后v->T。
别忘了此处u,v不能相邻。
d i s S [ i ] disS[i] disS[i]为i距起点距离, d i s T [ i ] disT[i] disT[i]为i距终点距离。答案即 d i s S [ u ] + k + d i s T [ v ] disS[u] + k + disT[v] disS[u]+k+disT[v]。
通过 d f s dfs dfs预处理,我们可以在 O ( n ) O(n) O(n)得出 d i s S disS disS和 d i s T disT disT。
使用传送的情况下,还可以再细分出两种答案。
通过对手限制的道路
消耗都是 1 e 9 1e9 1e9,所以传送越早越好。答案就是 1 e 9 1e9 1e9。
如果S和T相邻的话,因为边权 < = 1 e 9 <=1e9 <=1e9,最后答案取min不会造成问题。
不通过对手限制的道路
不妨先试举几个m。
如果对方的m为0,那么答案就是最小的 ( d i s S [ u ] + d i s T [ v ] ) (disS[u] + disT[v]) (disS[u]+disT[v])然后+k。
如果对方的m为1,那么答案就是第二小的 ( d i s S [ u ] + d i s T [ v ] ) (disS[u] + disT[v]) (disS[u]+disT[v])然后+k。
朴素的想法是,暴力求出所有u,v的可能组合,其中的第m+1小 ( d i s S [ u ] + d i s T [ v ] ) + k (disS[u] + disT[v])+k (disS[u]+disT[v])+k就是答案。但是复杂度到达 n 2 n^2 n2,会tle。
直接寻找第k小显然超时。我们可以反向思考另一个问题:给出一个数字x,x在是第几小?如果能在 O ( n l o g n ) O(nlog\ n) O(nlog n)的级别以内解决这个新问题,我们只需要再套上 O ( l o g v ) O(log\ v) O(log v)二分即可获得答案。
此处反向思考是经典的第k小问题。给出例题
如何解决新问题?
我们枚举u,即固定了 d i s [ u ] dis[u] dis[u],只需要获取所有满足 d i s S [ u ] + d i s T [ v ] < = x disS[u] + disT[v] <= x disS[u]+disT[v]<=x即 d i s T [ v ] < = x − d i s S [ u ] disT[v] <= x - disS[u] disT[v]<=x−disS[u]。
我们可以提前维护一个升序的 d i s T disT disT,再进行一次二分即可获得答案。总复杂度是 O ( n l o g n ) O(nlog\ n) O(nlog n)的
此处需注意u,v不能相邻。在得到答案后,
还需枚举u的邻边y,如果 d i s S [ u ] + d i s T [ y ] < = x disS[u] + disT[y] <= x disS[u]+disT[y]<=x答案需减一。
以及考虑 d i s S [ u ] + d i s T [ u ] < = x disS[u] + disT[u] <= x disS[u]+disT[u]<=x
总结
现在我们有三部分答案
- 不使用传送,即 d i s T [ S ] disT[S] disT[S]
- 使用传送,并通过对手设置路段,即1e9
- 使用传送,并不通过对手设置路段,即二分出的x
三者最小即为答案。
代码如下
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll N = 1e5 + 5;
int n, m, k, S, T;
vector<pll> e[N];
ll disS[N], disT[N]; //距起点和终点的距离
ll tmp[N]; //维护升序的disT用来二分
void dfs(int u, int fa, ll *dis) {for (auto &[v, w] : e[u]) {if (v == fa) continue;dis[v] = dis[u] + w;dfs(v, u, dis);}
}
bool check(ll x) {ll sum = 0;for (int u = 1; u <= n; u++) {sum += upper_bound(tmp + 1, tmp + 1 + n, x - disS[u]) - tmp - 1;for (auto &[v, w] : e[u]) { //邻边if (disS[u] + disT[v] <= x) sum--;}if (disS[u] + disT[u] <= x) sum--; //自身}return sum > m;
}
void solve() {cin >> n >> m >> k >> S >> T;for (int i = 1; i < n; i++) {int u, v, w;cin >> u >> v >> w;e[u].push_back({v, w});e[v].push_back({u, w});}dfs(S, 0, disS);dfs(T, 0, disT);for (int i = 1; i <= n; i++) tmp[i] = disT[i];sort(tmp + 1, tmp + 1 + n);ll l = 0, r = 1e18;while (l <= r) {ll mid = l + (r - l) / 2;if (check(mid)) {r = mid - 1;} else {l = mid + 1;}}cout << min({l + k, (ll)1e9, disT[S]}) << endl;
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);solve();return 0;
}