問題概要

連結な重み付き無向グラフを考える。
このグラフから辺を取り去る際の報酬をその辺の重みと定義するとき、得られる報酬の最大値を求めよ。ただし、グラフの連結性を崩してはならない。

主な制約
$2 \le $ 頂点数 $N $ $\le 2 \times 10^5$
$N-1 \le $ 辺数 $\le 2 \times 10^5$
$-10^9 \le $ 重み $ \le 10^9$

考察

辺を取り去る操作を実装することは難しいので、辺が全くない状態から辺を繋いで連結なグラフを構築する作業を考えて、その過程で採用されなかった辺を「取り去った辺」と見なすことにする。

$$報酬額 = (重みの総和) - (使った辺の重みの総和)$$

だから、結局は右辺第二項の最小化問題に帰着し、Kruscal 法の範疇と分かる。負辺を取り除くメリットはないので負辺は必ず使う、という微修正を典型的な Kruscal 法の実装にかけて素直に実装する。

実装

ほぼ典型的なKruscal 法の実装のまま。ループ内の if 文に追加で w > 0 を課しただけ。

typedef long long ll;
struct edge_k {
    ll u;
    ll v;
    ll weight;
    // ordering by weight 
    bool operator<(const edge_k &rhs) const {
        if (weight == rhs.weight) {
            if (u == rhs.u) {
                return v < rhs.v;
            } else {
                return u < rhs.u;
            }
        } else {
            return weight < rhs.weight;
        }
    }
    edge_k(const ll &u, const ll &v, const ll &w) : u(u), v(v), weight(w) {}
    edge_k() {}
};

int main() {
    using kruskal_graph = vector<edge_k>;
    ll total_w = 0;
    // read input
    auto n = in<ll>();
    auto m = in<ll>();
    kruskal_graph g;
    rp(i, m) {
        ll a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        total_w += c;
        g.emplace_back(a, b, c);
    }

    auto kruskal = [&](kruskal_graph &g) -> ll {
        // sort by weight
        sort(g.begin(), g.end());
        ll res = 0;

        // use your union_find
        union_find uf(n);
        for (auto e : g) {
            ll w  = e.weight;
            ll u = e.u;
            ll v = e.v;

            // ignore negative edges
            if (uf.same(u, v) && w > 0) continue;

            // add edges
            res += w;
            uf.merge(u, v);
        }
        return res;
    };

    ll ans = total_w - kruskal(g);
    print(ans);
}