「CF2174D」Secret Message

    「CF2174D」Secret Message

    CF2174D

    给出一个包含 nn 个点 mm 条边的带权无向图。

    你需要找出 n−1n - 1 条边,使得这些边的权值之和最小,且不构成一棵树。

    数据范围:2≤n≤2×1052 \leq n \leq 2 \times 10^5,n−1≤m≤2×105n - 1 \leq m \leq 2 \times 10^5,1≤wi≤1091 \leq w_i \leq 10^9。

    时空限制:22s / 256256MiB。

    Solution

    首先将所有边按照边权从小到大排序为 e1,e2,…,eme_1, e_2, \dots, e_m,记权值分别为 w1,w2,…,wmw_1, w_2, \dots, w_m。

    首先考虑前 n−1n - 1 条边,如果不构成一棵树则结束。否则我们可以得到前 n−1n - 1 条边构成的生成树,考虑在该生成树上替换若干条边。

    替换一条边

    对于一条非树边 (x,y,z)(x, y, z),我们只能替换不在从 xx 到 yy 路径上的边。所以现在要求的是,不在从 xx 到 yy 路径上的最大边。

    一个简单的做法是,取出最大的树边 (xm,ym,zm)(x_m, y_m, z_m),若最大树边不在从 xx 到 yy 的路径上,则我们要求的就是这条边。

    否则将该最大树边断开,得到两个根节点分别为 xm,ymx_m, y_m 的树。相当于是给定根节点,查询不在从根到 xx 的路径上的最大边。可以使用类似换根 dp 的方法统计出。

    (邪修:使用树剖维护。每次查询时,将 xx 到 yy 路径上的所有边加上 −∞-\infty,然后查询全局最大值)

    替换两条以上的边

    对于替换两条以上的边,我们可以证明 sum−wn−1−wn−2+wn+wn+1\mathrm{sum} - w_{n - 1} - w_{n - 2} + w_n + w_{n + 1} 是答案的一个上界。其实际意义也就是将 en−1,en−2e_{n - 1}, e_{n - 2} 替换成 en,en+1e_n, e_{n + 1}。

    首先,如果有 en−1e_{n - 1} 或 en−2e_{n - 2} 不在 ene_n 或 en+1e_{n + 1} 的管辖路径上,则必定有一个更优秀的 “替换一条边” 的方案。

    所以我们假设 en−1,en−2e_{n - 1}, e_{n - 2} 都在 ene_n 与 en+1e_{n + 1} 的管辖路径上,此时断开 en−1,en−2e_{n - 1}, e_{n - 2} 会形成三个连通块,然而 en,en+1e_n, e_{n + 1} 连接的是同一个连通块(可以画图理解),最后会剩下两个连通块,所以此时的方案是合法的。显然该方案是 “替换两条以上的边” 之中代价最小的。

    时间复杂度 O(n+mlog⁡m)\mathcal{O}(n + m \log m)。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    using u64 = unsigned long long;
    
    #define debug(a) std::cout << #a << "=" << (a) << ' '
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    const int N = 200100, M = 200100;
    const i64 inf = 1e18;
    
    int n, m;
    std::tuple<int, int, int> e[M];
    
    int fa[N];
    int get(int x) {
        return fa[x] == x ? x : fa[x] = get(fa[x]);
    }
    
    struct Graph {
        std::vector< std::vector< std::pair<int, int> > > table;
    
        void init(int _n) {
            table.assign(_n + 1, {});
        }
    
        void add_edge(int u, int v, int w) {
            table[u].push_back({v, w});
        }
    } G;
    
    i64 f[N], g[N];
    
    void dp1(int u, int fu) {
        for (auto [v, w] : G.table[u]) {
            if (v == fu) {
                continue;
            }
            f[v] = w, dp1(v, u);
            chmax(f[u], f[v]);
        }
    }
    
    void dp2(int u, int fu, i64 pre) {
        i64 fir = -inf, sec = -inf;
        g[u] = pre;
        for (auto [v, w] : G.table[u]) {
            if (v == fu) {
                continue;
            }
            chmax(g[u], f[v]);
            if (f[v] > fir) {
                sec = fir, fir = f[v];
            } else {
                chmax(sec, f[v]);
            }
        }
        for (auto [v, w] : G.table[u]) {
            if (v == fu) {
                continue;
            }
            dp2(v, u, std::max(pre, f[v] == fir ? sec : fir));
        }
    }
    
    void work() {
        std::cin >> n >> m;
    
        for (int i = 1; i <= m; i ++) {
            int x, y, z;
            std::cin >> x >> y >> z;
    
            e[i] = {z, x, y};
        }
    
        std::sort(e + 1, e + 1 + m);
    
        i64 ans = inf;
        i64 sum = 0;
        for (int i = 1; i < n; i ++) {
            sum += std::get<0>(e[i]);
        }
    
        std::iota(fa + 1, fa + 1 + n, 1);
        for (int i = 1; i < n; i ++) {
            auto [z, x, y] = e[i];
    
            int p = get(x), q = get(y);
            if (p == q) {
                std::cout << sum << '\n';
                return;
            }
    
            fa[p] = q;
        }
    
        G.init(n);
    
        std::iota(fa + 1, fa + 1 + n, 1);
        for (int i = 1; i < n - 1; i ++) {
            auto [z, x, y] = e[i];
    
            fa[get(x)] = get(y);
            G.add_edge(x, y, z), G.add_edge(y, x, z);
        }
    
        for (int i = 1; i <= n; i ++) {
            f[i] = g[i] = -inf;
        }
    
        auto [mz, rx, ry] = e[n - 1];
        dp1(rx, 0), dp2(rx, 0, -inf);
        dp1(ry, 0), dp2(ry, 0, -inf);
    
        for (int i = n; i <= m; i ++) {
            auto [z, x, y] = e[i];
    
            if (get(x) == get(y)) {
                chmin(ans, sum - mz + z);
            } else {
                chmin(ans, sum - std::max(g[x], g[y]) + z);
            }
        }
    
        if (n >= 3 && m >= n + 1) {
            chmin(ans, sum - std::get<0>(e[n - 1]) - std::get<0>(e[n - 2]) + std::get<0>(e[n]) + std::get<0>(e[n + 1]));
        }
    
        if (ans == inf) {
            ans = -1;
        }
        std::cout << ans << '\n';
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        int T;
        std::cin >> T;
        
        while (T --) {
            work();
        }
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/