20230410 训练记录：最小瓶颈路 / lca-526互联

初识最小瓶颈路其实是上海那道著名的铜牌题，其次就是 P1396 营救。

P1967 [NOIP2013 提高组] 货车运输 / 最小瓶颈路

https://www.luogu.com.cn/problem/P1967

\(\mathcal O(m \log m + (n + q)\log n)\) 最大生成树（森林）两点间最小边权，直接在倍增 lca 向上爬的时候更新答案。

问题反过来，最小生成树上的瓶颈（最大边权）也是一样的，双倍经验捏：LOJ #136. 最小瓶颈路

注意不能使用 dep[u] = dep[p] + 1 而将 \(p = 0\)，换言之不能 dfs(i, 0)，为了避免重复访问，dfs 的时候不记父亲节点。

展开代码

void dfs(int u) {
    for (int i = h[u]; i; i = graph[i].t) {
        if (int v = graph[i].f; !dep[v]) {
            dep[v] = dep[u] + 1, f[v][0] = u, w[v][0] = graph[i].w;
            dfs(v);
        }
    }
}
// ...
for (int i = 1; i <= n; i++) if (!dep[i]) {
    dep[i] = 1;
    dfs(i);
    f[i][0] = i; // 之前因为这里无脑设成 f[u][0] = p 而一直出错
    w[i][0] = INT_MAX;
}

哇呜呜，怎么还有加强版，学！

LOJ#137. 最小瓶颈路（加强版）/ Kruskal 重构树

https://loj.ac/p/137 + https://loj.ac/p/6021(双倍经验)

使用 Kruskal 重构树来求解。 ~~感觉已经看过太多太多次克鲁斯卡尔重构树了，但是都没有认真学过。~~

最小瓶颈路
= 最小生成树两点间简单路径上的最大值
= Kruskal 重构树上两点之间的 \(\mathop{lca}\) 的权值。

建立 Kruskal 重构树就是在做 Kruskal 的过程中，原本要合并 \(u\) 和 \(v\)，现在改为新建一个点 \(t\)，连边 \(u \leftarrow t \rightarrow v\)，\(t\) 的点权设为 \(u, v\) 的边权。

这方法对最大生成树两点间最小边权也适用。

void Kruskal() {
    sort(edge + 1, edge + 1 + m, cmp);
    for (int i = 1; i <= n; ++i) ff[i] = i;
    for (int i = 1; i <= m; ++i) {
        int fu = find(edge[i].u), fv = find(edge[i].v);
        if (fu != fv) {
            val[++cnt] = edge[i].dis;
            ff[cnt] = ff[fu] = ff[fv] = cnt;
            add(fu, cnt), add(cnt, fu);
            add(fv, cnt), add(cnt, fv);
        }
    }
}

倍增可以得 \(75 \rm pts\)，树剖可以得 \(90 \rm pts\)。

100pts（Tarjan / RMQ 求 lca）

满分得配合 Tarjan / RMQ 求 \(\mathop{lca}\)，这俩都是离线算法~~，不过看起来貌似 RMQ 更厉害一点~~。

草，怎么还要复习稀疏表，咋写的来着。

用 \(f_{i, j}\) 表示 \([i, i + 2^j)\) 的答案，只要有 \(x \mathop{op} x = x\) 就可以用。递推就是倍增：

\[f_{i, j} = f_{i, j - 1} \mathop{op} f_{i + 2^{j - 1}, j - 1} \]
反正就是 \([i, i + 2^{j - 1}) \cup [i + j^{j - 1}, i + 2 \times 2 ^ {j - 1}) = [i, i + 2^j)\)。

查询的时候就拆成 \([l, l + 2 ^ t) \cup [r - 2^t + 1, r]\)。

结论是：记 \(\text{pos}_u\) 为 \(u\) 在欧拉序中第一次出现的位置，则

\[\text{pos}_{\mathop{lca}(u, v)} = \min\limits_{k = u}^v\{ \text{pos}_k \} \]

意为从 \(u\) 走到 \(v\) 经过欧拉序最小的节点就是 \(\mathop{lca}(u, v)\)。

记个板子，明天再背。

void dfs(int now, int fa) {
  dpth[now] = dpth[fa] + 1;
  sec[++cnt] = now;
  pos[now] = cnt;

  for (int i = head[now]; i; i = e[i].nxt) {
    if (fa != e[i].to) {
      dfs(e[i].to, now);
      sec[++cnt] = now;
    }
  }
}

void init() {
  dfs(2 * n - 1, 0);
  for (int i = 1; i <= 4 * n; i++) {
    dp[i][0] = sec[i];
  }
  for (int j = 1; j <= 19; j++) {
    for (int i = 1; i + (1 << j) - 1 <= 4 * n; i++) {
      dp[i][j] = dpth[dp[i][j - 1]] < dpth[dp[i + (1 << (j - 1))][j - 1]]
                     ? dp[i][j - 1]
                     : dp[i + (1 << (j - 1))][j - 1];
    }
  }
}

int lca(int x, int y) {
  int l = pos[x], r = pos[y];
  if (l > r) {
    swap(l, r);
  }
  int k = log2Values[r - l + 1];
  return dpth[dp[l][k]] < dpth[dp[r - (1 << k) + 1][k]]
             ? dp[l][k]
             : dp[r - (1 << k) + 1][k];
}

现在，终于可以来看看这道题了。

Life is a game

https://ac.nowcoder.com/acm/contest/24872/H

先学了一个单词 threshold(/ˈθreʃˌhoʊld/): 门槛，瓶颈。

题意

\(n\) 个点 \(m\) 条边，点权表示这个点拥有的金币（只能获得一次），边权表示前往联通的点至少需要有 \(w\) 金币。
多组询问：从 \(x\) 点出生，初始拥有 \(k\) 个金币，最多可以得到的金币数为多少？
\(n, m, q \leq 10^5; a_i \leq 10^4; k, w \leq 10 ^ 9\)

实际的边权为 \(w_i - a_u, w_i - a_v\)，随后在 Kruskal 重构树上不断向上爬，直到 \(w_{x, i} \gt k\)，此时 \(a_x + k\) 即为所求。

展开代码

#include <bits/stdc++.h>

using ll = long long;

const int N = 200010, M = N * 2;

int n, m, q;
ll a[N];

int val[N], t = 0, f[N][20];
ll w[N][20];

struct edge {
    int f, w, t;
    bool operator< (const edge &_) const {
        return w < _.w;
    }
} mst[N];

int p[N];
int find(int x) {
    return p[x] = p[x] == x ? x : find(p[x]);
}

void Kruskal() {
    std::sort(mst + 1, mst + m + 1);
    for (int i = 1; i <= n * 2; i++)
        p[i] = i;

    t = n;
    for (int i = 1, edgs = 0; i <= m; i++) {
        int u = find(mst[i].f);
        int v = find(mst[i].t);
        int w = mst[i].w;

        if (u != v) {
            a[++t] = a[u] + a[v];
            p[u] = p[v] = f[u][0] = f[v][0] = t;
            ::w[u][0] = w - a[u];
            ::w[v][0] = w - a[v];
            edgs += 1;
        }

        if (edgs == n - 1)
            break;
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", a + i);

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        mst[i] = {u, w, v};
    }

    Kruskal();

    a[0] = a[t];
    int lg = std::__lg(t) + 1;
    for (int j = 1; j <= lg; j++) {
        for (int i = 1; i <= t; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
            w[i][j] = std::max(w[i][j - 1], w[f[i][j - 1]][j - 1]);
        }
    }

    while (q --) {
        int x, k;
        scanf("%d%d", &x, &k);

        for (int i = lg; ~i; i--) {
            if (w[x][i] <= k)
                x = f[x][i];
        }

        printf("%lld\n", a[x] + k);
    }

    return 0;
}

总结

今天一直在学习树上问题，希望在天梯赛之前能够磨练自己的数据结构和树论水平，等天梯赛选上西安之后再复习数论。慢慢地要改变之前的学习方式了，得开始背一背板子，定期做做复习工作。

加油喵。

20230410 python day7 day

collection 20230410日记java

lca

20230410日记java list

笔记lca