python/TangDou/AcWing/LCA/356.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 100010, M = 300010;
const int INF = 0x3f3f3f3f;

int f[N][16];    // f[i][k]表示树上的某节点i向上走2^k步到达的节点
PII dist[N][16]; // d[i][k]表示树上的某节点i向上走2^k步到达的节点最长距离和次长距离
int depth[N];    // 深度数组

// Kruskal结构体
struct Edge {
    int a, b, c; // 从a到b边权为c
    bool flag;   // 是不是最小生成树的树边
    const bool operator<(const Edge &t) const {
        return c < t.c;
    }
} edge[M];

// 邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 并查集
int p[N];
int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

// 树上倍增求任意点到2^0,2^1,2^2,...的距离，注意，不是任意两点间最长距离和次长距离,是半成品，不是成品！
int bfs(int root) {
    queue<int> q;
    q.push(root);
    depth[root] = 1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (!depth[v]) {
                depth[v] = depth[u] + 1; // 记录深度
                q.push(v);
                f[v][0] = u; // 记录2^0->t,描述父节点

                //-->下面是与普通的倍增不一样的代码<--
                // v->u 的最大距离:w[i],与次大距离:-INF,递推初始化数据
                dist[v][0] = {w[i], -INF};

                for (int k = 1; k <= 15; k++) { // 倍增
                    int x = f[v][k - 1];        // 设v跳2 ^(k-1)到达的是x点
                    f[v][k] = f[x][k - 1];      // x点跳2^(k-1)到达的终点就是v跳2^k的终点

                    //-->下面是与普通的倍增不一样的代码<--
                    // ①最大边权
                    dist[v][k].first = max(dist[v][k - 1].first, dist[x][k - 1].first);
                    // ②次大边权
                    if (dist[v][k - 1].first == dist[x][k - 1].first)                          // 如果前半部分最大距离等于后半部分最大距离
                        dist[v][k].second = max(dist[v][k - 1].second, dist[x][k - 1].second); // 整体次大=max(前半次大，后半次大)
                    else if (dist[v][k - 1].first < dist[x][k - 1].first)                      // 如果前半最大小于后半最大
                        dist[v][k].second = max(dist[v][k - 1].first, dist[x][k - 1].second);  // 整体次大=max(前半最大，后半次大)
                    else                                                                       // 如果前半最大大于后半最大
                        dist[v][k].second = max(dist[v][k - 1].second, dist[x][k - 1].first);  // 整体次大=max(前半次大，后半最大)
                }
            }
        }
    }
}

// 因为同时需要同步修改最大值和次大值，所以采用了地址符&引用方式定义参数
//  m1:最大值，m2：次大值
void update(int &m1, int &m2, PII x) {
    if (m1 == x.first)
        m2 = max(m2, x.second);
    else if (m1 < x.first)
        m2 = max(m1, x.second), m1 = x.first;
    else
        m2 = max(m2, x.first);
}

// 功能：添加上a->b的边,边权是c,去掉a->b的原来最大或次大，比最小生成树多出来多少边权(c- m1 或者 c-m2)
// 思路：利用倍增思想,找出a->b之间的最大距离和次大距离
// 具体是-m1,还是-m2，要区别对待，如果c=m1,就是-m2,否则-m1
int lca(int a, int b, int c) {
    if (depth[a] < depth[b]) swap(a, b);  // 保证a的深度大于b的深度
    int m1 = -INF, m2 = -INF;             // 最大边，次大边初始化
    for (int k = 15; k >= 0; k--)         // 由小到大尝试
        if (depth[f[a][k]] >= depth[b]) { // 让a向上跳2^k步
            update(m1, m2, dist[a][k]);   // 记录a到向上走2^k步这段范围内，遇到的最大和次大长度
            a = f[a][k];                  // 标准lca
        }

    // 当a与b不是同一个点时
    // 此时两者必然是depth一样的情况，同时向上查询2^k，必然可以找到LCA
    if (a != b) {
        for (int k = 15; k >= 0; k--)
            if (f[a][k] != f[b][k]) {
                update(m1, m2, dist[a][k]); // 记录a到向上走2^k步这段范围内，遇到的最大和次大长度
                update(m1, m2, dist[b][k]); // 记录b到向上走2^k步这段范围内，遇到的最大和次大长度
                // 注意写在a=f[a][k],b=f[b][k]上方，要不a,b就被改了，此句就不对了
                a = f[a][k], b = f[b][k];
            }
        // 此时a和b到lca下同一层 所以还要各跳1步=跳2^0步
        update(m1, m2, dist[a][0]);
        update(m1, m2, dist[b][0]);
    }
    // m1,m2中装的是 a->b之间的最大边权和次大边权，现在给了一个新边权c,它能替换m1,m2,还是谁也替换不了呢？
    // 因为m1,m2是最小生成树中的最大边权和次大边权，c >= m1 > m2
    // if(c==m1) 那么c能去替换m2,获取的收益就是c-m2
    // if(c> m1) 那么c能去替换m1,获取的收益就是c-m1
    return c == m1 ? c - m2 : c - m1;
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // 并查集初始化
    for (int i = 1; i <= n; i++) p[i] = i;
    // 邻接表初始化
    memset(h, -1, sizeof h);

    // Kruskal
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edge[i] = {a, b, c, 0};
    }

    // 按边权排序+最小生成树
    sort(edge, edge + m);

    LL sum = 0, ans = 1e18;

    // Kruskal
    for (int i = 0; i < m; i++) {
        int a, b, c;
        a = find(edge[i].a), b = find(edge[i].b), c = edge[i].c;
        if (a != b) {
            p[a] = b;

            sum += c;         // 最小生成树的边权总和
            edge[i].flag = 1; // 标识为最小生成树中的边,因为后面要枚举非树边
            // 将最小生成树中的树边单独构建一个图出来
            add(edge[i].a, edge[i].b, c), add(edge[i].b, edge[i].a, c);
        }
    }

    // 倍增预处理,记录任意点向上2^k步的最大值，次大值，深度等信息，后面lca会用到
    // 以任意点为根
    bfs(1);

    // 用非树边去尝试替换最小生成树中的边，然后取min
    for (int i = 0; i < m; i++)
        if (!edge[i].flag) { // 枚举非树边
            int a = edge[i].a, b = edge[i].b, c = edge[i].c;
            ans = min(ans, sum + lca(a, b, c));
            // 在最小生成树中，将a,b两点间连接一条长度为c的边,相对最小生成树，长度会增加多少呢？
        }
    // 输出
    printf("%lld\n", ans);
    return 0;
}