AtCoder ABC 328 E - Modulo MST (？色, 475 点)

next_combination を使った！　普通に STL の next_permutation() でもできる。

• 問題へのリンク

問題概要

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

このグラフの全域木をすべて考えたときの、全域木に含まれる辺の重みの総和を で割ったあまりの最小値を求めよ。

制約

• 
• 

考えたこと

が小さいので、 個の辺から 個の辺を選ぶ方法を全探索すればよいと考えた。

具体的に場合の数を見積もってみると......

• 
• 

なので、最大でも 通りである。これは全探索しても間に合う。

具体的に全探索するには、next_combination が使えるし、next_permutation() でもいい。

コード

#include <bits/stdc++.h>
using namespace std;

// next combination
template<class T> bool next_combination(T &bit, int N) {
    T x = bit & -bit, y = bit + x;
    bit = (((bit & ~y) / x) >> 1) | y;
    return (bit < (1LL << N));
}

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

    // constructor
    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    // core methods
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(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)];
    }
};

// edge
struct Edge {
    int from, to;
    long long weight;
    Edge(int f = 0, int t = 0, long long w = 0) : from(f), to(t), weight(w) {}
};


int main() {
    long long N, M, K;
    cin >> N >> M >> K;
    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        long long u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        edges[i] = Edge(u, v, w);
    }
    
    long long res = 1LL<<62;
    long long bit = (1LL << (N-1)) - 1;
    do {
        long long tmp = 0;
        bool ok = true;
        UnionFind uf(N);
        for (int i = 0; i < M; ++i) {
            if (bit >> i & 1) {
                auto [f, t, w] = edges[i];
                if (uf.same(f, t)) ok = false;
                uf.merge(f, t);
                tmp += w;
            }
        }
        if (ok) res = min(res, tmp % K);
    } while (next_combination(bit, M));
    
    cout << res << endl;
}