「JSOI 2008」最小生成树计数

题目大意：求一张 $n$ 个点 $m$ 条边的无向图的最小生成树个数，保证具有相同权值的边不超过 $10$ 条。$n \leq 100, m \leq 1000$

用到一个性质：对于每一棵最小生成树，每种权值的边的数量一定；连完每种权值的边后，图的连通情况相同。

由于具有相同权值的边不超过 $10$ 条，可以 $dfs$ 计算每种权值的边的连接方案数。

#include <cstdio>
#include <algorithm>
 
const int mod = 31011;
 
struct Edge {
    int u, v, w;
    bool operator < (const Edge &rhs) const {
        return w < rhs.w;
    }
} e[1005];
 
struct Node {
    int l, r, n;
} a[1005];
 
int fa[105], n, m, cnt, sum, ans = 1;
 
int find(int x) { //不路径压缩, 便于分裂
    return x == fa[x] ? x : find(fa[x]);
}
void dfs(int cur, int k, int tot) {
    if (cur > a[k].r) {
        sum += tot == a[k].n;
        return;
    }
    dfs(cur + 1, k, tot);
    int fx = find(e[cur].u), fy = find(e[cur].v);
    if (fx != fy) {
        fa[fx] = fy;
        dfs(cur + 1, k, tot + 1);
        fa[fx] = fx;
    }
}
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    std::sort(e + 1, e + m + 1);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    a[++cnt].l = 1;
    for (int i = 1; i <= m; ++i) {
        int fx = find(e[i].u), fy = find(e[i].v);
        if (fx != fy) fa[fx] = fy, ++a[cnt].n, ++sum;
        if (e[i].w != e[i+1].w)
            a[cnt].r = i, a[++cnt].l = i + 1;
    }
    if (sum != n - 1) { puts("0"); return 0; }
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= cnt; ++i) {
        sum = 0;
        dfs(a[i].l, i, 0);
        if (sum) (ans *= sum) %= mod;
        for (int j = a[i].l; j <= a[i].r; ++j) {
            int fx = find(e[j].u), fy = find(e[j].v);
            if (fx != fy) fa[fx] = fy;
        }
    }
    printf("%d\n", ans);
    return 0;
}

时间复杂度 $O(\dfrac{2^{10}nm}{10})$