問題概要

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

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

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

制約

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

考えたこと

つまり、各辺 $e$ について

元のグラフ全体の最小全域木の重み
元のグラフから辺 $e$ を除去した場合の最小全域木の重み

とが異なれば、その辺 $e$ は絶対必要ということになるので、その重みを追加していく。一回の最小全域木の計算には $O(M \log N)$ の計算量がかかかる。よってすべての辺に対して実施したのでは $O(M^{2} \log N)$ の計算量となって間に合わない。

そこで、まずは一回元のグラフ上で最小全域木 $T$ を求めることにする。「絶対必要」な辺は少なくとも $T$ には含まれるはずである。よって、 $T$ に含まれる辺だけ考えればよい。 $T$ は木なので、辺の本数は $N-1$ 本になる。よって計算量は $O(MN \log N)$ へと改善された。これなら間に合う。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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>;
const long long INF = 1LL<<60;
long long calc(int N, const vector<Edge> &edges, vector<int> &res, int id = -1) {
    long long cost = 0;
    res.clear();
    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);
    }
    if (res.size() == N - 1) return cost;
    else return INF;
}

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());
    vector<int> kouho, tmp;
    long long base = calc(N, edges, kouho);
    long long num = 0, res = 0;
    for (auto id : kouho) {
        if (calc(N, edges, tmp, id) > base) ++num, res += edges[id].first;
    }
    cout << num << " " << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1350 There is No Alternative (ICPC アジア 2014 F) (450 点)

問題概要

制約

考えたこと

コード