题意
求一张图不同的的最小生成树个数，对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<bits/stdc++.h>
#define N 1005
using 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 <class T>
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<b.w;}
int find(int x) {return fa[x] == x ? x : find(fa[x]);}
void kruskal()
{
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;++i)
{
if(e[i].w!=e[i-1].w) rgb[++cnt]=(Rgb){i,i,0};
else rgb[cnt].r=i;
int fx=find(e[i].u),fy=find(e[i].v);
if(fx!=fy)
{
fa[fx]=fy;
rgb[cnt].v++;
tot++;
}
}
}
void dfs(int choose,int col,int now)
{
if(now==rgb[col].r+1)
{
if(choose==rgb[col].v) ++sum;
return;
}
dfs(choose,col,now+1);
if(choose<rgb[col].v)
{
int fx=find(e[now].u),fy=find(e[now].v);
if(fx!=fy)
{
fa[fx]=fy;
dfs(choose+1,col,now+1);
fa[fx]=fx;fa[fy]=fy;
}
}
}
int main()
{
read(n);read(m);
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i) read(e[i].u),read(e[i].v),read(e[i].w);
kruskal();
if(tot<n-1) {cout<<0<<endl;return 0;}
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=cnt;++i)
{
sum=0;
dfs(0,i,rgb[i].l);
ans=ans*sum%mod;
for(int j=rgb[i].l;j<=rgb[i].r;++j)
{
int fx=find(e[j].u),fy=find(e[j].v);
if(fx!=fy) fa[fx]=fy;
}
}
cout<<ans<<endl;
return 0;
}
法二：矩阵树定理
不会，留坑
矩阵树定理可以\((n^3)\)统计无向连通图的生成树个数
大概意思就是枚举边权i，将除了边权i之外的所有边全部加入图中，然后缩点，用矩阵树定理即可统计边权i的选择方案数，最后同样乘起来即可（口胡）
转载于:https://www.cnblogs.com/Chtholly/p/11426256.html
