最小生成树计数
#include <bits/stdc++.h> using namespace std; const int maxn=1010; const int mod=31011; struct edge{ int u,v,w; bool operator<(const edge & b)const { return w<b.w; } }a[maxn]; struct node{ int l,r,num; }b[maxn]; int n,m,fa[maxn],num,tot,ans=1,sum; int fin(int x) { if (x == fa[x]) return x; return fin(fa[x]); } void dfs(int i,int now,int k){ if (now==b[i].r+1){ if (k==b[i].num) sum++; return; } int u=fin(a[now].u),v=fin(a[now].v); if (u!=v){ fa[u]=v; dfs(i,now+1,k+1); fa[u]=u;fa[v]=v; } dfs(i,now+1,k); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 1; i <= m; i++) { scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w); } sort(a + 1, a + m + 1); for (int i = 1; i <= m; i++) { if (a[i].w != a[i - 1].w) { b[++num].l = i; b[num - 1].r = i - 1; } int u = fin(a[i].u), v = fin(a[i].v); if (u != v) { fa[u] = v; tot++; b[num].num++; } } b[num].r = m; if (tot != n - 1) { printf("0 "); return 0; } for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 1; i <= num; i++) { sum = 0; dfs(i, b[i].l, 0); ans = ans * sum % mod; for (int j = b[i].l; j <= b[i].r; j++) { int u = fin(a[j].u), v = fin(a[j].v); if (u != v) fa[u] = v; } } printf("%d ", ans); return 0; }