题面

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对$31011$的模就可以了。（具有相同权值的边不会超过10条）

思路

这题有点ex啊,不知道矩阵树定理或者最小生成树两个特殊性质就gg了。(显然我gg了)

最小生成树有两个特殊性质

1.如果一张图存在多个最小生成树，他们边权的组成是一样的，比如一棵最小生成树的边权组成是$(1,1,2,2,3)$那么其它的边权组成也是$(1,1,2,2,3)$。

2.不同的生成树中,某一种权值的边连接完成后,形成的联通块状态是一样的

那么我们就可以从小到大加边，然后把每种边权可能的方案数相乘就是答案了（注意判断能否联通，如果跑第一遍最小生成树都建不出来那就不连通输出$0$就好了），接下来请看图。

由此我们来引出联通块的概念，如果是最小生成树，那么连任意一条边的之前，两个端点一定在不同的联通块内，而且这个联通块只受到比他权值小或相等的边的影响，不然最小生成树还不如把大的边替换成它。那么这题大致思路就十分明确了，对于每一种边权枚举子集然后连接，并且每次枚举都要把联通块还原回连这种边权之前的状态(这种边权子集任意连接后的联通块状态是一样的，所以对于下一种边权来说之前联通块的状态一定固定)，所以开三个fa数组并查集维护记录就好了，相当于是滚动存储。然后直接爆枚出解即可，我的算法和别人的不大一样，不需要撤回(并查集断边)，因为我是枚举子集的，所以可以用路径压缩。时间复杂度为$O(2^{该边权条数}*不同边权种类数*n)$，因为不同边权种类数变大的话每种边权条数就会变少，所以大致最坏复杂度大概是$O(100*100*1024)$可以通过此题。

代码

#include<bits/stdc++.h>
#define Mod 31011
#define Maxm 1005
#define Maxn 105
using namespace std;
vector<int> vec[Maxm];
int n,m,anss=1,lsh[Maxm],fa[Maxn],cnt=0,tree_tot[Maxm],graph_tot[Maxm],last_fa[Maxn],tmp_fa[Maxn],num=0,ans=0;
struct edge{int u,v,w;}t[Maxm];
inline void read(int &x){int f=1;x=0;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}x*=f;}
inline int getfa(int x){if (x==fa[x]) return x;return fa[x]=getfa(fa[x]);}
bool cmp(edge a,edge b){return a.w<b.w;}
inline int count_one(int x){int res=0;for (int i=0;i<10;i++) if ((x>>i)&1) res++;return res;}
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++) fa[i]=i,tmp_fa[i]=i;
	for (int i=1;i<=m;i++) read(t[i].u),read(t[i].v),read(t[i].w),lsh[i]=t[i].w;
	sort(lsh+1,lsh+m+1);
	int cnt=unique(lsh+1,lsh+m+1)-lsh-1;
	for (int i=1;i<=m;i++) t[i].w=lower_bound(lsh+1,lsh+cnt+1,t[i].w)-lsh;
	sort(t+1,t+m+1,cmp);
	for (int i=1;i<=m;i++) vec[t[i].w].push_back(i),graph_tot[t[i].w]++;
	for (int i=1;i<=m;i++){int fx=getfa(t[i].u),fy=getfa(t[i].v);if (fx==fy) continue;fa[fx]=fy;num++;tree_tot[t[i].w]++;if (num==n-1) break;} 
	if (num!=n-1) return puts("0"),0;
	for (int i=1;i<=cnt;i++)
	{
		for (int j=1;j<=n;j++) last_fa[j]=tmp_fa[j];ans=0;
		for (int E=0;E<=(1<<graph_tot[i])-1;E++)
		{
			int cnnt=count_one(E);
			bool flag=0;
			if (cnnt==tree_tot[i]) 
			{
				for (int j=1;j<=n;j++) fa[j]=last_fa[j];
				for (int j=0;j<graph_tot[i];j++) {if ((E>>j)&1){int fx=getfa(t[vec[i][j]].u),fy=getfa(t[vec[i][j]].v);if (fx==fy) {flag=1;break;} fa[fx]=fy;}}
				if (flag==0) {for (int j=1;j<=n;j++) tmp_fa[j]=fa[j];ans++;ans%=Mod;}
			}	
		}
		anss=(anss*ans)%Mod;
	}
	cout<<anss<<endl;
	return 0;
}