传送门
正解是并查集+矩阵树定理。
但由于数据范围小搜索也可以过。
我们需要知道最小生成树的两个性质：
- 不同的最小生成树中,每种权值的边出现的个数是确定的
- 不同的生成树中,某一种权值的边连接完成后,形成的连通块状态是一样的
那么可以根据乘法原理按权值分步，将每一步得到的结果相乘。
每次分步的计算可以用搜索/矩阵树定理来实现。
代码：
#include<bits/stdc++.h>
#define mod 31011
#define N 15
#define M 1005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,m,ans=1,fa[N],siz[M],last,cols;
struct edge{int u,v,w;}e[M];
vector<edge>g[M];
inline bool cmp(edge a,edge b){return a.w<b.w;}
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline int Find(int x){return x==fa[x]?x:Find(fa[x]);}
inline int dfs(int col,int dep,int pos,int ret=0){
if(dep==g[col].size())return pos==siz[col];
if(pos<siz[col]){
int fx=Find(g[col][dep].u),fy=Find(g[col][dep].v);
if(fx!=fy)fa[fx]=fy,ret+=dfs(col,dep+1,pos+1),fa[fx]=fx;
}
if(pos+g[col].size()>=siz[col]+dep+1)ret+=dfs(col,dep+1,pos);
return ret;
}
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);
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;++i)fa[i]=i;
int tot=0;
for(int i=1;i<=m;++i){
if(e[i].w!=e[i-1].w)++tot;
g[tot].push_back(e[i]);
int fx=find(e[i].u),fy=find(e[i].v);
if(fx!=fy)++siz[tot],fa[fx]=fy,++cols;
}
if(cols<n-1){printf("0");return 0;}
for(int i=1;i<=n;++i)fa[i]=i;
for(int i=1;i<=tot;++i){
(ans*=dfs(i,0,0))%=mod;
for(int j=0;j<g[i].size();++j){
int fx=find(g[i][j].u),fy=find(g[i][j].v);
fa[fx]=fy;
}
}
printf("%d",ans);
return 0;
}