思路：
暴力+并查集
枚举边的子集，用并查集判断两个点联不联通
代码：
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 30; piii e[N]; int fa[N], tmp[(1<<25) + 10]; int n, m, top = 0; int Find(int x) { if(x == fa[x]) return x; else return Find(fa[x]); } void dfs(int i, int cnt, int len) { if(m-i+1 + cnt < n-1) return ;//这个剪枝很优秀 if(i == m+1) { if(cnt == n-1) tmp[++top] = len; return ; } dfs(i+1, cnt, len); int u = Find(e[i].fi.fi), v = Find(e[i].fi.se); if(u != v) { fa[u] = v; dfs(i+1, cnt+1, len+e[i].se); fa[u] = u; } } int main() { int l, r, q; scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d %d %d", &e[i].fi.fi, &e[i].fi.se, &e[i].se); } for (int i = 1; i <= n; i++) fa[i] = i; dfs(1, 0, 0); sort(tmp+1, tmp+1+top); scanf("%d", &q); while(q--) { scanf("%d %d", &l, &r); printf("%d ", upper_bound(tmp+1, tmp+1+top, r) - lower_bound(tmp+1, tmp+1+top, l)); } return 0; }