最小生成树计数

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2003 字
按权分组枚举子集统计最小生成树个数
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1492
// 题意：n 点 m 边简单无向图，求不同的最小生成树有多少个，答案对 31011 取模，同权边不超过 10 条。
// 思路：Kruskal 按权值分组，组内枚举候选边的所有子集，统计边数等于该组应加入边数且不成环的子集个数，各组结果相乘。
// 复杂度：O(m log m + m*2^10) 时间 / O(n+m) 空间
// 易错点：子集必须达到该组 Kruskal 实际加入的边数（即极大森林），否则会把没连满的方案也算进去；模数 31011 不是质数不能做除法。
#include <bits/stdc++.h>
using namespace std;
const int MOD = 31011;
struct Edge{
    int u, v;
    long long w;
};
struct DSU{
    int p[105];
    void init(int n){
        for(int i = 1; i <= n; i++) p[i] = i;
    }
    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    bool unite(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return false;
        p[a] = b;
        return true;
    }
};
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    vector<Edge> e(m);
    for(int i = 0; i < m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e.begin(), e.end(), [](const Edge &a, const Edge &b){
        return a.w < b.w;
    });
    DSU cur, tmp;
    cur.init(n);
    long long ans = 1;
    int i = 0;
    while(i < m){
        int j = i;
        while(j < m && e[j].w == e[i].w) j++;
        vector<int> cand;
        for(int k = i; k < j; k++){
            if(cur.find(e[k].u) != cur.find(e[k].v)) cand.push_back(k);
        }
        tmp = cur;
        int need = 0;
        for(size_t t = 0; t < cand.size(); t++){
            if(tmp.unite(e[cand[t]].u, e[cand[t]].v)) need++;
        }
        long long ways = 0;
        int sz = (int)cand.size();
        for(int mask = 0; mask < (1 << sz); mask++){
            if(__builtin_popcount((unsigned)mask) != need) continue;
            DSU chk = cur;
            bool ok = true;
            for(int b = 0; b < sz && ok; b++){
                if(!(mask & (1 << b))) continue;
                if(!chk.unite(e[cand[b]].u, e[cand[b]].v)) ok = false;
            }
            if(ok) ways++;
        }
        ans = ans * ways % MOD;
        cur = tmp;
        i = j;
    }
    cout << ans << '\n';
    return 0;
}
最小生成树计数

正文

一本通·提高篇的其它内容
