福州品牌网站建设,小狗做爰网站,服装设计公司主要做什么,装饰网站建设网前言
本题解较为基础#xff0c;推导如何得出二分解题思路。
题目大意
给出无根带权树#xff0c;双方采取最佳策略#xff0c;求节点S-T的最短路。
有两种操作#xff1a;
我方至多可以使用一次传送#xff0c;花费k元从a传送到b#xff08;ab不能相邻#xf…前言
本题解较为基础推导如何得出二分解题思路。
题目大意
给出无根带权树双方采取最佳策略求节点S-T的最短路。
有两种操作
我方至多可以使用一次传送花费k元从a传送到bab不能相邻。敌方至多可以把m条道路的传送消耗设置为1e9元单向设置如设置a-b消耗不影响b-a。
思路
显然的答案可以分两种情况。
不使用传送
对方的操作不用看答案直接S-T的最短路。
使用传送
设传送起点为u传送终点为v。总体流程为S-u然后传送到v然后v-T。 别忘了此处uv不能相邻。 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]kdisT[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的可能组合其中的第m1小 ( 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小显然超时。我们可以反向思考另一个问题给出一个数字xx在是第几小如果能在 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)的 此处需注意uv不能相邻。在得到答案后 还需枚举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 pairll, ll;
const ll N 1e5 5;
int n, m, k, S, T;
vectorpll 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;
}
