跳转至

CF609E

知识点

  • 最小生成树
  • MST
  • LCA
  • Kruskal
  • 倍增

题意简述

给定一个 \(n\) 个点,\(m\) 条边的图,对其中每条边,求包含这条边的最小生成树的边权和。保证图中无自环1

数据范围:\(1 \le n, m \le 2\cdot 10^5\)\(1 \le w_i \le 10^9\)

解题思路

乍一看很不可做,但是想通了,就是道模板题了吧。

首先先求出原图的任意一个 MST,把 MST 上的所有边都标记一下。

对于每条边 \((u, v)\),如果在 MST 上,那么直接输出 MST 的边权和即可;

否则找到 \(u\)\(v\) 在树上的那条链上的最大边权,减去这条边的边权,加上 \((u, v)\) 的边权即可。

(这样也可以 \(O(m\log n)\) 求次小生成树?)

代码实现

核心部分已用高亮标出。

Code
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
#define LL long long

namespace io {
    template <typename T> inline void read(T & _x) {
        int f = 0, ch; _x = 0;
        while(!isdigit(ch = getchar())) f |= ch == '-';
        while(isdigit(ch)) _x = _x * 10 + ch - '0', ch = getchar();
        if(f) _x = -_x;
    }
    template <typename T, typename ... Args> inline void read(T &_f, Args& ... args) {
        read(_f), read(args ...);
    }
    inline void _deal(char ch) { putchar(ch); }
    template <typename T> inline void _deal(T _x) {
        if (_x < 0) putchar('-'), _x = -_x;
        if (_x > 9) _deal(_x / 10);
        putchar(_x % 10 + '0');
    }
    inline void write() {}
    template <typename T, typename ... Args> inline void write(T _f, Args ... args) {
        _deal(_f), write(args...);
    }
}

const int N = 2e5 + 5;
const int M = 2e5 + 5;

int n, m, cnt, first[N];
int uu[M], vv[M], ww[M], rk[N], vis[N];
int lg2[N] = {-1}, dep[N], f[N][20], w[N][20];
LL sum;

struct EDGE {
    int to, _next, wt;
} e[M * 2];

struct DSU {
    static const int MS = N;
    int fa[MS], siz[MS];
    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    void join(int x, int y) {
        int px = find(x), py = find(y);
        if(px != py) {
            if(siz[px] < siz[py])
                std::swap(px, py);
            fa[py] = px;
            siz[px] += siz[py];
        }
    }
    bool check(int x, int y) {
        return find(x) == find(y);
    }
    void init(int ss) {
        for(int i = 1; i <= ss; ++i)
            fa[i] = i, siz[i] = 1;
    }
} dsu;

void add(int u, int v, int wei) {
    e[cnt].to = v, e[cnt]._next = first[u], e[cnt].wt = wei;
    first[u] = cnt++;
}

void connect(int u, int v, int wei) {
    add(u, v, wei), add(v, u, wei);
}

bool cmp(int ii, int jj) {
    return ww[ii] < ww[jj];
}

void Kruskal() {
    int cntEdge = 0;
    for(int i = 1; i <= m; ++i)
        rk[i] = i;
    dsu.init(n);
    std::sort(rk + 1, rk + m + 1, cmp);
    for(int i = 1; i <= m; ++i) {
        if(cntEdge == n - 1)
            break;
        if(dsu.check(uu[rk[i]], vv[rk[i]]))
            continue;
        sum += ww[rk[i]], ++cntEdge;
        dsu.join(uu[rk[i]], vv[rk[i]]);
        connect(uu[rk[i]], vv[rk[i]], ww[rk[i]]);
        vis[rk[i]] = 1;
    }
}

void dfs(int x, int p, int weight) {
    dep[x] = dep[p] + 1;
    f[x][0] = p, w[x][0] = weight;
    for(int i = 1; i <= lg2[dep[x]]; ++i) {
        f[x][i] = f[f[x][i - 1]][i - 1];
        w[x][i] = std::max(w[x][i - 1], w[f[x][i - 1]][i - 1]);
    }
    for(int i = first[x]; ~i; i = e[i]._next) {
        int y = e[i].to;
        if(y == p)
            continue;
        dfs(y, x, e[i].wt);
    }
}

int solve(int u, int v) {
    if(dep[u] < dep[v])
        std::swap(u, v);
    int tmp = dep[u] - dep[v], ans = -1;
    for(int i = 0; i <= lg2[dep[u]]; ++i)
        if(tmp >> i & 1) {
            ans = std::max(ans, w[u][i]);
            u = f[u][i];
        }
    if(u == v)
        return ans;
    for(int i = lg2[dep[u]]; i >= 0; --i)
        if(f[u][i] != f[v][i]) {
            ans = std::max(ans, w[u][i]);
            ans = std::max(ans, w[v][i]);
            u = f[u][i], v = f[v][i];
        }
    return std::max(ans, std::max(w[u][0], w[v][0]));
}

int32_t main() {
    io::read(n, m);
    memset(first, -1, sizeof(first));
    for(int i = 1; i <= n; ++i)
        lg2[i] = lg2[i >> 1] + 1; 
    for(int i = 1; i <= m; ++i)
        io::read(uu[i], vv[i], ww[i]);
    Kruskal();
    dfs(1, 0, 0);
    for(int i = 1; i <= m; ++i) {
        if(vis[i])
            io::write(sum, '\n');
        else
            io::write(sum - solve(uu[i], vv[i]) + ww[i], '\n');
    }
    return 0;
}