题意

求一张图不同的的最小生成树个数，对31011取模，满足\(n\leq 100,m\leq 1000,w\leq 1e9\) 且每种边权的边数不超过10

思路

定理：对于不同的最小生成树方案，相同边权的边数不变

证明（伪）：假设比当前权值小的边都选择完了（不一定加进了最小生成树），那么当前权值为\(w\)的边一定要尽量的选，合并越多连通块越好。于是假设将当前权值的所有边加入可以合并\(k\)次连通块，由于有没有用的边存在，我们会将它们删掉，但仍然一定会保证这\(k\)次连通块合并仍然存在（前面说的加边越多越好），由于选择一条边即表示合并一次连通块，所以会选择\(k\)条边，显然这是一个定值

备注：其实从上面的证明中容易发现，\(k\)条边的每一种合理选择方案所影响的连通块状态应该是一致的（只要有一种方案使得\(a\)与\(b\)相连，即使其他方案选择的边不同，也都会使\(a\)与\(b\)相连）

法一：暴力枚举

于是，我们求出最小生成树中有权值相同的边的个数，对于每一种权值，我们对其进行dfs，找到k条有用的边，这样算作一种方案，由于权值相同的边不会超过10，所以复杂度不超过\(2^{10}\)

时间复杂度为\(O(2^{10}m)\)

Code

#include
    
     #define N 1005using namespace std;const int mod = 31011;int n,m,fa[N];struct E {int u,v,w;} e[N];struct Rgb {int l,r,v;} rgb[N];int cnt,ans=1,sum,tot;template 
     
      void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}bool cmp(E a,E b) {return a.w
     
    

法二：矩阵树定理

不会，留坑

矩阵树定理可以\((n^3)\)统计无向连通图的生成树个数

大概意思就是枚举边权i，将除了边权i之外的所有边全部加入图中，然后缩点，用矩阵树定理即可统计边权i的选择方案数，最后同样乘起来即可（口胡）