ABC 328

Table of Contents

E - Modulo MST

$N = 8$ のときの完全グラフのときの辺の数は $\displaystyle \frac{N(N-1)}{2} = \frac{8 \times 7}{2} = 28$ でここから $N-1=7$ ほんの辺を選ぶ選び方は $_{28}\mathrm{C}_7 = 1,184,040$ 通りなので全探索が間に合う。 各頂点について自身を含めて他のどの頂点に辺を張るかということを考える場合でも $N^{N-1} = 8^7 = 2,097,152$ こっちの方法でも間に合う。

$N-1$ 本の辺を張る実装

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m, k;
    cin >> n >> m >> k;

    vector<tuple<ll, ll, ll>> es;
    rep(i, m) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        es.emplace_back(u, v, w);
    }

    ll ans = INF;
    auto dfs = [&](auto dfs, int depth, vint used) {
        if (used.size() == n - 1) {
            dsu uf(n);
            ll sum = 0;
            for (int i : used) {
                auto [u, v, w] = es[i];
                if (uf.same(u, v))
                    return;
                uf.merge(u, v);
                sum += w;
                sum %= k;
            }
            chmin(ans, sum);
            return;
        }
        if (depth == m) {
            return;
        }

        dfs(dfs, depth + 1, used);
        used.push_back(depth);
        dfs(dfs, depth + 1, used);
    };

    dfs(dfs, 0, {});
    cout << ans << endl;
}

辺が存在するかわからないがとりあえず考えうるパターンを確認する実装

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m, k;
    cin >> n >> m >> k;

    map<pair<int, int>, ll> es;
    rep(i, m) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        es[{u, v}] = w;
        es[{v, u}] = w;
    }

    ll ans = INF;
    rep(i, intpow(n, n - 1)) {
        ll t = i;
        vint v;
        rep(j, n - 1) {
            v.push_back(t % n);
            t /= n;
        }

        dsu uf(n);

        rep(j, n - 1) {
            int a = j, b = v[j];
            if (es.count({a, b})) {
                uf.merge(a, b);
            }
        }
        int ok = 1;
        rep(j, n) {
            if (!uf.same(0, j))
                ok = 0;
        }
        if (!ok)
            continue;

        ll sum = 0;
        rep(j, n - 1) {
            sum += es[{j, v[j]}];
            sum %= k;
        }
        chmin(ans, sum);
    }

    cout << ans << endl;
}