洛谷 P4208 Lutece 2726 最小生成树计数模版

https://www.luogu.com.cn/problem/P4208

题意

求个节点, 条边的无向图的不同的最小生成树个数.

问题本身的性质

多尝试几个样例可以发现, 同一个图的所有最小生成树中, 相同边权的边的数量是一定相等的.

通过 Kruscal 算法的贪心过程容易证明这个结论: 从权值最小的边开始选择, 假如一种方案选择了条权值为的边, 若另一种方案选了比更多的边, 则说明原来的方案不是最优解; 若选了更少的边, 则新方案不是最优解. 因此, 满足最小的条件下, 生成树中相同权值的边数量相同.

借助以上性质, 可以先求出一棵最小生成树, 然后分别考虑生成树上不同权值的边的答案, 通过乘法原理得到结果. 然而, 直接用组合数计算是不行的, 因为任选条权值为的边, 不能保证仍然能够与其他权值的边组合成生成树.

通过矩阵树定理, 可以利用行列式计算图的所有生成树个数. 为了固定其余边权的边不变, 只考虑选取某个边权的边的情况, 可以通过并查集的方式将原有生成树上其他权值的边都缩成一点, 只保留要求权值的边, 则缩点后图的生成树数量就是满足条件的原图生成树数量.

矩阵树定理

定义图的 Laplacian 矩阵 ,

其中是节点 i 的度数, 是节点 u 和 v 的边数.

image.png

例如, 上图的 Laplacian 矩阵是

则图的生成树个数为 , 其中是去掉行列, 任取 .

详细的证明可参考知乎文章.

行列式

显然不能用循环群定义和余子式定义直接求.

考虑高斯消元转换为上三角阵. 由于本题中模数不一定是质数, 不能直接进行除法 (疑似浮点数的精度可以通过此题), 但可以考虑用辗转相除法进行消元, 规避除法运算. 辗转相除法本身不会造成太高的复杂度, 仍可以视作级别.

template <typename T>
T det(vector<vector<T>> a, T mod, int n = -1) {
    T symbol = 1;
    if (n == -1) n = a.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            while (a[i][i] != 0) {
                T d = a[j][i] / a[i][i] % mod;
                for (int k = i; k < n; k++) {
                    a[j][k] -= a[i][k] * d % mod;
                    a[j][k] = (a[j][k] % mod + mod) % mod;
                }
                swap(a[i], a[j]);
                symbol = -symbol;
            }
            swap(a[i], a[j]);
            symbol = -symbol;
        }
    }

    T ans = symbol;
    for (int i = 0; i < n; i++) {
        ans *= a[i][i];
        ans %= mod;
    }
    return (ans + mod) % mod;
}

代码

Kruscal 最小生成树已经将边排序过了, 枚举相同权值的边比较方便.

class kruskal {
    struct edge {
        int to, from;
        int w;
        edge(int to = 0, int from = 0, int w = 0) : to(to), from(from), w(w) {}
    } e[MAXM * 2];

    int ecnt;
    int n;
    int fa[MAXN];
    int color[MAXN];
    int find(int u) { return (fa[u] == u) ? u : fa[u] = find(fa[u]); }

    static bool cmp(const edge& a, const edge& b) { return a.w < b.w; }

   public:
    kruskal(int n) {
        this->n = n;
        ecnt = 0;
    }

    void adde(int to, int from, int w) { e[++ecnt] = edge(to, from, w); }

    int64 solve_count() {
        sort(e + 1, e + ecnt + 1, cmp);
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
        }
        int pos = 1;
        int max_weight = 0;
        vector<edge> tree_edges;
        tree_edges.reserve(n - 1);
        while (tree_edges.size() < n - 1 && pos <= ecnt) {
            edge& now = e[pos];
            pos++;
            if (find(now.from) != find(now.to)) {
                max_weight = now.w;
                tree_edges.push_back(now);
                fa[find(now.from)] = find(now.to);
            }
        }
        if (tree_edges.size() < n - 1) return 0;

        int64 ans = 1;
        int cur_edge = 1;
        while (cur_edge <= ecnt && e[cur_edge].w <= max_weight) {
            int cur_weight = e[cur_edge].w;
            for (int i = 1; i <= n; i++) {
                fa[i] = i;
            }
            for (auto& e : tree_edges) {
                if (e.w != cur_weight) {
                    fa[find(e.from)] = find(e.to);
                }
            }
            int color_cnt = 0;
            memset(color, -1, sizeof color);
            for (int i = 1; i <= n; i++) {
                if (color[find(i)] == -1) {
                    color[find(i)] = color_cnt;
                    color_cnt++;
                }
                color[i] = color[find(i)];
            }
            vector<vector<int64>> laplacian(color_cnt,
                                            vector<int64>(color_cnt, 0));
            while (e[cur_edge].w == cur_weight && cur_edge <= ecnt) {
                int u = color[e[cur_edge].from];
                int v = color[e[cur_edge].to];
                laplacian[u][v] -= 1;
                laplacian[v][u] -= 1;
                laplacian[u][u] += 1;
                laplacian[v][v] += 1;
                cur_edge++;
            }

            ans *= det<int64>(laplacian, MOD, color_cnt - 1);
            ans %= MOD;
        }

        return ans;
    }
};

本文采用署名-相同方式共享 4.0 国际许可协议，转载请注明出处。