??给出一张 \(n\) 个点，\(m\) 条边的带权无向图，求不同最小生成树的数量。同一权值的边至多有 \(k=10\) 条。
??根据 Kruskal 算法的思想，按照边权从小到大的顺序处理边，每次处理同一权值的所有边。
??处理同一权值的边时，考虑图的联通情况。边权较小的边已经把图连接成了数个联通块，而这些联通块在加入了这些边后会形成新的联通块。加入这些边前后的联通块都是确定的，不同权值的边的选择互不影响。可以把加入一类权值的边看成一个步骤。由于不同权值的边之间互不影响，相当于步骤之间互不影响，可以应用乘法原理。
??加入一类权值的边的过程相当于是给出一些点（对应原图中的联通块）和一些边（对应连接联通块的边，去掉自环）求不同生成森林的个数，而生成森林的个数就是每一个联通块的生成树的个数的乘积，可以用矩阵树定理求出联通块生成树个数对应的行列式，再用高斯消元求值。
??由于本题模数 \(31011=3*10337\) 不是素数，\(k\) 又很小，可以直接用 long double 类型求出行列式的近似值四舍五入。复杂度为 \(O(m+nk^2)\)。
代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod=31011;
const int maxn=105,maxm=1e3+5,maxk=15;
struct edge{ int u,v,w; };
inline bool operator < (edge a,edge b){ return a.w<b.w; }
edge ed[maxm];
int fa[maxn];
int ff(int u){ return fa[u]==u?u:ff(fa[u]); }
vector<int> e[maxn];
vector<int> arr,tmp;
int id[maxn];
bool vis[maxn];
ld a[maxk][maxk];
void dfs(int u){
int i,v;
id[u]=tmp.size(); tmp.push_back(u); vis[u]=false;
for (i=0;i<e[u].size();i++)
if (vis[v=e[u][i]]) dfs(v);
}
ll solve(){
int i,j,k,p,n;
ld t,ans=1;
n=tmp.size()-1;
for (i=0;i<n;i++){
p=i;
for (j=i;j<n;j++)
if (fabs(a[j][i])>fabs(a[p][i])) p=j;
if (p-i&1) ans=-ans;
for (j=0;j<n;j++) swap(a[i][j],a[p][j]);
for (j=i+1;j<n;j++){
t=a[j][i]/a[i][i];
for (k=0;k<n;k++)
a[j][k]-=a[i][k]*t;
}
}
for (i=0;i<n;i++) ans*=a[i][i];
return (ll)(ans+0.5);
}
int main(){
int i,j,k,n,m;
int u,v,l,r;
ll ans;
scanf("%d%d",&n,&m);
for (i=0;i<m;i++)
scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);
sort(ed,ed+m);
for (i=1;i<=n;i++) fa[i]=i;
r=0; ans=1;
while (r<m){
l=r;
while (r<m&&ed[r].w==ed[l].w) r++;
for (i=l;i<r;i++){
u=ff(ed[i].u); v=ff(ed[i].v);
if (u==v) continue;
if (!vis[u]){ vis[u]=true; arr.push_back(u); }
if (!vis[v]){ vis[v]=true; arr.push_back(v); }
e[u].push_back(v); e[v].push_back(u);
}
for (i=0;i<arr.size();i++) if (vis[arr[i]]){
memset(a,0,sizeof(a)); tmp.clear(); dfs(arr[i]);
for (j=0;j<tmp.size();j++){
for (k=0;k<e[u=tmp[j]].size();k++){
a[id[u]][id[e[u][k]]]-=1; a[id[u]][id[u]]+=1;
}
e[u].clear(); fa[u]=tmp[0];
}
ans=ans*solve()%mod;
}
}
for (i=1;i<=n;i++) if (ff(i)!=ff(1)){
puts("0"); return 0;
}
printf("%lld\n",ans);
return 0;
}原文：https://www.cnblogs.com/Kilo-5723/p/12207582.html