正解矩阵树
不会
显然最小生成树每个长度的边的数量是不变的
而且题目说：具有相同权值的边不会超过10条。
暴力 dfs 枚举所有相同长度的边，看看有多少种方案
然后就过了
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; struct edge { int a,b,v; }e[1005];//存边 inline bool cmp(const edge a,const edge b){return a.v<b.v;} struct node { int l,r,s; }d[1005];//存排序后每个长度的边的左右边界和在最小生成树中的总数 int n,m,cnt,ans=1,sum; int fa[105]; inline int find(int x){ return fa[x]==x ? x : fa[x]=find(fa[x]); } inline void dfs(int i,int j,int s) { if(j>d[i].r){ if(s==d[i].s) sum++; return; }//如果到边界了就判断一波是否符合要求 int xa=find(e[j].a),xb=find(e[j].b); if(xa!=xb)//如果可以加入就考虑加入 { fa[xa]=xb;//更新一波并查集 dfs(i,j+1,s+1); fa[xa]=xa;//恢复并查集 } dfs(i,j+1,s);//考虑不加入的情况 } int main() { cin>>n>>m; for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v); //以下为最小生成树模板 sort(e+1,e+m+1,cmp); for(int i=1;i<=n;i++) fa[i]=i; int res=0; for(int i=1;i<=m;i++) { if(e[i].v>e[i-1].v)//顺便计算一下d数组 d[++cnt].l=i,d[cnt-1].r=i-1; int xa=find(e[i].a),xb=find(e[i].b); if(xa==xb) continue; d[cnt].s++; fa[xa]=xb; res++; } d[cnt].r=m; if(res<n-1）{ cout<<"0"; return 0; }//判断一波 for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=cnt;i++) { sum=0; dfs(i,d[i].l,0);//强行dfs找方案 ans=(ans*sum)%31011; for(int j=d[i].l;j<=d[i].r;j++) { int xa=find(e[j].a),xb=find(e[j].b);//更新一波状态 if(xa==xb) continue; fa[xa]=xb; } } cout<<ans; return 0; }