题目传送门

Description

给一个有边权的无向图,求权值在 $[L,R]$ 之间的生成树个数。

$n\leq 20,m\leq 25$

Solution

$2^m$ 直接枚举。

用并查集判断连通。

注意剪枝。

题解说用啥可持久化并查集,我直接暴力清零...

维护一下区间内前缀和,查询可以 $O(1)$ 。

Code

/*
 * @Name: 219A.cpp
 * @Author: Lovely_XianShen
 * @Date: 2019-11-06 10:55:16
 * @Aqours!Sunshine!!
 */
#include<bits/stdc++.h>
using namespace std;

inline int read() {
    int a = 0; char x = getchar();
    while (x < '0' || x > '9')x = getchar();
    while (x >= '0' && x <= '9')a = (a << 3) + (a << 1) + x - 48, x = getchar();
    return a;
}

int n, m, q, askl[10005], askr[10005], a[1000005], fa[25], minl = 0x3f3f3f3f, maxr = -0x3f3f3f3f;

int ans;

struct edg {
    int u, v, w;
} e[30];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main() {
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        e[i].u = read();
        e[i].v = read();
        e[i].w = read();
    }
    q = read();
    for (int i = 1; i <= q; i++)
        askl[i] = read(), askr[i] = read(), minl = min(askl[i], minl), maxr = max(maxr, askr[i]);
    for (int i = 1; i < (1 << m); i++) {
        ans = i;
        int tot = 0, flag = 1;
        while (ans) {
            ans &= (ans - 1); tot++;
        }
        if (tot != n - 1)flag = 0;
        if (flag) {
            ans = 0;
            for (int j = 1; j <= n; j++)
                fa[j] = j;
            for (int j = 1; j <= m; j++)
                if (i & (1 << (j - 1))) {
                    ans += e[j].w;
                    int f1 = find(e[j].u), f2 = find(e[j].v);
                    if (f1 == f2) {
                        flag = 0;
                        break;
                    } else fa[f1] = f2;
                }
            if (flag && ans >= minl && ans <= maxr)a[ans - minl + 1]++;
        }
    }
    for (int i = 1; i <= maxr - minl + 1; i++)
        a[i] += a[i - 1];
    for (int i = 1; i <= q; i++)
        cout << a[askr[i] - minl + 1] - a[askl[i] - minl] << endl;
    return 0;
}