https://www.lydsy.com/JudgeOnline/problem.php?id=1016
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。
无外乎两种：K算法和P算法（当然还有第三种但是我不会（滑稽）
P算法没法解于是用K算法。
发现K算法的正确性后其实我们需要做的工作就是从K算法找到一些边，可以用另一些边权一样的边替换并且是一棵生成树即可。
于是我们枚举即可。
（当然你会有两个问题：1.为什么边权一样即可替换，2.前面的边的操作对后面边是否有影响？）
（所以暴力选手不过脑子的话就很轻松的敲完代码走人了（比如我））
（实际为两个定理，分别为：
1.不同的最小生成树中,每种权值的边出现的个数是确定的。
2.不同的生成树中,某一种权值的边连接完成后,形成的联通块状态是一样的 。
百度一下。）
（https://blog.csdn.net/jarily/article/details/8902402可能这个解释靠谱些？）
#include<algorithm>#include<iostream>#include<cstring>#include<cctype>#include<cstdio>#include<vector>#include<cmath>using namespace std;typedef long long ll;const int N=101;const int M=1010;const int p=31011;inline int read(){ ???int X=0,w=0;char ch=0; ???while(!isdigit(ch)){w|=ch==‘-‘;ch=getchar();} ???while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); ???return w?-X:X;}struct node{ ???int u,v,w;}e[M];struct range{ ???int l,r;}a[M];int fa[N],t[M],n,m,k,sum;inline bool cmp(node a,node b){ ???return a.w<b.w;}int find(int x){ ???if(fa[x]==x)return x; ???return find(fa[x]);}inline void unionn(int x,int y){ ???fa[x]=y;}inline void destory(int x,int y){ ???fa[x]=x;fa[y]=y;}void dfs(int l,int r,int d,int w){ ???if(l>r){ ???????if(d==t[w])sum=(sum+1)%p; ???????return; ???} ???if(r-l+1+d<t[w])return; ???int u=find(e[l].u),v=find(e[l].v); ???if(u!=v&&d<t[w]){ ???????unionn(u,v); ???????dfs(l+1,r,d+1,w); ???????destory(u,v); ????} ???dfs(l+1,r,d,w);}int main(){ ???n=read(),m=read(); ???for(int i=1;i<=m;i++){ ???????e[i].u=read(),e[i].v=read(),e[i].w=read(); ???} ???sort(e+1,e+m+1,cmp); ???for(int i=1;i<=n;i++)fa[i]=i; ???int cnt=0; ???for(int i=1;i<=m;i++){ ???????if(e[i].w!=e[i-1].w){ ???????????a[++k].l=i;a[k-1].r=i-1; ???????} ???????int u=e[i].u,v=e[i].v; ???????u=find(u),v=find(v); ???????if(u!=v)t[k]++,cnt++,unionn(u,v); ???} ???a[k].r=m; ???if(cnt!=n-1){ ???????puts("0");return 0; ???} ???int ans=1; ???for(int i=1;i<=n;i++)fa[i]=i; ???for(int i=1;i<=k;i++){ ???????if(!t[i])continue; ???????sum=0; ???????dfs(a[i].l,a[i].r,0,i); ???????ans=(ll)ans*sum%p; ???????for(int j=a[i].l;j<=a[i].r;j++){ ???????????int u=e[j].u,v=e[j].v; ???????????u=find(u),v=find(v); ???????????if(u!=v)unionn(u,v); ???????} ???} ???printf("%d\n",ans); ???return 0;}+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +
+++++++++++++++++++++++++++++++++++++++++++
BZOJ1016：[JSOI2008]最小生成树计数——题解
原文地址：https://www.cnblogs.com/luyouqi233/p/8996369.html