問題概要

頂点数 $N$ 、辺数 $M$ の、連結な重み付き無向単純グラフ $G$ が与えられる。

このグラフの「最小全域木」はさまざまなものが考えられるが、そのすべてに含まれるような辺の集合を考える。

その集合の要素数と、その集合に含まれる辺の重みの総和を求めよ。

制約

$3 \le N \le 500$
$N-1 \le M \le \min(50000, \frac{N(N-1)}{2})$

愚直な解法

まずは愚直な解法を考えてみましょう。グラフ $G$ の各辺 $e$ に対して、

元のグラフ $G$ の最小全域木の重み
元のグラフから辺 $e$ を除去してできるグラフ $G-e$ の最小全域木の重み

とを比較します。これらが異なれば、その辺 $e$ は絶対必要ということになります。よってすべての辺 $e$ に対して上記の処理を実施すれば解くことができます。一回の最小全域木の計算には $O(M \log N)$ の計算量がかかかりますので、全体の計算量は $O(M^{2} \log N)$ となります。しかしこれでは間に合いません。

最初に最小全域木を求める

そこで、まずは一回元のグラフ上で最小全域木 $T$ を求めることにしましょう。

このとき、「絶対必要」な辺は少なくとも $T$ には含まれるはずです。よって、先ほどのように $G$ に含まれるすべての辺 $e$ について調べるのではなく、 $T$ に含まれる辺 $e$ のみを考えればよいです。これによって、調べるべき辺の本数を大きく減らすことができます。

実際 $T$ は木ですので、辺の本数は $N-1$ 本です。よって計算量は $O(MN \log N)$ へと改善されます。これなら間に合います。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Union-Find
struct UnionFind {
    vector<int> par;

    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

// 辺を表す構造体
using pint = pair<int, int>;  // 両端点
using Edge = pair<long long, pint>;  // (重み, 両端点)

int main() {
    // 入力
    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        edges[i] = Edge(w, pint(u, v));
    }

    // 各辺を重みの小さい順にソート
    sort(edges.begin(), edges.end());

    // id 番目の辺を削除した場合の最小全域木を求める関数
    // id == -1 のときは、通常の最小全域木を求める
    // res は、最小全域木をなす辺番号が格納される
    auto calc = [&](vector<int> &res, int id = -1) -> long long {
        long long cost = 0;
        res.clear();

        // Kruskal 法
        UnionFind uf(N);
        for (int i = 0; i < edges.size(); ++i) {
            if (i == id) continue;
            int u = edges[i].second.first, v = edges[i].second.second;
            if (uf.issame(u, v)) continue;
            res.push_back(i);
            cost += edges[i].first;
            uf.merge(u, v);
        }

        // N-1 本に満たない場合は連結でない
        if (res.size() < N - 1) return (1LL<<60);
        return cost;
    };
    
    // もとのグラフの最小全域木を求める
    vector<int> mst;
    long long base = calc(mst);

    // 最小全域木 mst に含まれる各辺 e を 1 本ずつ除去して調べる
    vector<int> dammy;
    long long num = 0, res = 0;
    for (auto id : mst) {
        if (calc(dammy, id) > base) {
            ++num;
            res += edges[id].first;
        }
    }
    cout << num << " " << res << endl;
}