F. Cheap Robot

給定一個無向連通圖，每條邊有邊權(quán)，路過需要消耗對應(yīng)的電量（邊權(quán)），有$k$個中心點，

問從$a?>b$，我們最少需要帶多少電，設(shè)最小為$C$，當(dāng)通過一條邊時，我們的電會減少（當(dāng)電不夠時即不能通過），當(dāng)經(jīng)過中心點時我們的電會立刻變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$C$，

比較簡單的想法：處理出任意兩個中心點對的最短路出來，最后我們只需要得到中心點對的升序$kruskal$最小生成樹，然后每次查詢兩點之間的$lca$的權(quán)值即可。

我們假設(shè)$dis[x]$為從$x$到達最近的中心點所需要的電量，

設(shè)我們以$T$電量到達了$u$點，那么我們要能夠到達終點（注意終點是一個中心點），那么一定有$T\ge dis[u]$，

也就是說如果離$u$最近的中心點不是終點，那么我們在$u$點的能量可以更新為$C?dis[u]$，且有$C?dis[u]\ge T$，

如果與$u$直接相連的邊為$v$，要能夠到達$v$，那么一定有$C?dis[u]\ge W_{u,v}$，$W_{u,v}$是邊權(quán)，

同時要使能從$v$到達終點，那么$C?dis[u]?W_{u,v}\ge dis[v]$也同樣成立，也就是有$C\ge dis[u]+dis[v]+w_{u,v}$，

滿足上面的式子，我們才可能通過一條邊，然后從某條邊走向終點，

所以我們可以把原本的一條邊的邊權(quán)轉(zhuǎn)化為$W_{u,v}=W_{u,v}+dis[u]+dis[v]$，跑一個升序$kruskal$最小生成樹，找$lca$權(quán)值即可

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e6 + 10;int n, nn, k, m, q, ff[N];ll value[N], dis[N];int head[N], vis[N], nex[N], to[N], cnt = 1;int fa[N], dep[N], sz[N], top[N], son[N], id[N], tot;struct Res {int u, v;ll w;void read() {scanf("%d %d %lld", &u, &v, &w);}bool operator < (const Res &t) const {return w < t.w;} }edge[N];struct Node {int u;ll w;bool operator < (const Node &t) const {return w > t.w;} };vector<Node> G[N];bool cmp(int x, int y) {return id[x] < id[y]; }int find(int rt) {return ff[rt] == rt ? rt : ff[rt] = find(ff[rt]); }void add(int x, int y) {to[cnt] = y;nex[cnt] = head[x];head[x] = cnt++; }void dfs1(int rt, int f) {fa[rt] = f, dep[rt] = dep[f] + 1, sz[rt] = 1, id[rt] = ++tot;for (int i = head[rt]; i; i = nex[i]) {if (to[i] == f) {continue;}dfs1(to[i], rt);sz[rt] += sz[to[i]];if (sz[son[rt]] < sz[to[i]]) {son[rt] = to[i];}} }void dfs2(int rt, int tp) {top[rt] = tp;if (!son[rt]) {return ;}dfs2(son[rt], tp);for (int i = head[rt]; i; i = nex[i]) {if (to[i] == fa[rt] || to[i] == son[rt]) {continue;}dfs2(to[i], to[i]);} }int lca(int x, int y) {while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) {swap(x, y);}x = fa[top[x]];}return dep[x] < dep[y] ? x : y; }void kruskal() {sort(edge + 1, edge + 1 + m);for (int i = 1; i < N; i++) {ff[i] = i;}for (int i = 1, cur = 1; i <= m && cur < n; i++) {int u = find(edge[i].u), v = find(edge[i].v);if (u ^ v) {cur++, nn++;ff[u] = ff[v] = nn;value[nn] = edge[i].w;add(nn, u), add(nn, v);}}dfs1(nn, 0), dfs2(nn, nn); }void Dijkstra() {priority_queue<Node> q;memset(vis, 0, sizeof vis);memset(dis, 0x3f, sizeof dis);for (int i = 1; i <= k; i++) {q.push({i, 0});dis[i] = 0;}while (q.size()) {int u = q.top().u;q.pop();if (vis[u]) {continue;}vis[u] = 1;for (auto to : G[u]) {if (dis[to.u] > dis[u] + to.w) {dis[to.u] = dis[u] + to.w;q.push({to.u, dis[to.u]});}}} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d %d %d %d", &n, &m, &k, &q);nn = n;for (int i = 1; i <= m; i++) {edge[i].read();G[edge[i].v].push_back({edge[i].u, edge[i].w});G[edge[i].u].push_back({edge[i].v, edge[i].w});}Dijkstra();for (int i = 1; i <= m; i++) {edge[i].w += dis[edge[i].u] + dis[edge[i].v];}kruskal();while (q--) {int u, v;scanf("%d %d", &u, &v);printf("%lld\n", value[lca(u, v)]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的F. Cheap Robot（kruskal 重构树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。