1016: [JSOI2008]最小生成树计数
题目：传送门
题解：
神题神题%%%
据说最小生成树有两个神奇的定理：
1、权值相等的边在不同方案数中边数相等
就是说如果一种方案中权值为1的边有n条
那么在另一种方案中权值为1的边也一定有n条
2、如果边权为1的边连接的点是x1,x2,x3
那么另一种方案中边权为1的边连接的也一定是x1,x2,x3
如果知道了这两条定理那就很好做了啊：
因为等权边的条数一定，那么我们就可以预处理求出不同边权的边的条数
题目很人道的保证了边权相同的边不会超过10条，那就可以光明正大的递归得出方案数了啊
接下来就要利用定理2了：
因为连接的点总是不变的，所以每一次选边是没有影响的，那么递归求出每一种权值边的方案数之后用乘法原理乘起来就ok
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define mod 31011
#define qread(x) x=read()
using namespace std;
inline int read()
{
int f=,x=;char ch;
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return f*x;
}
struct node
{
int x,y,c,next;
}a[];int n,m,sum;
int fa[];
int findfa(int x)
{
if(x==fa[x])return x;
return findfa(fa[x]);
}
bool cmp(node n1,node n2)
{
return n1.c<n2.c;
}
int d[],s[];
void dfs(int k,int t,int i)//当前选的是第k种边，已经选了t条，当前位置为第i条边
{
if(i==s[k]+)
{
if(t==d[k])
sum++,sum%=mod;
return ;
}
int fx=findfa(a[i].x),fy=findfa(a[i].y);
if(fx!=fy)
{
fa[fx]=fy;
dfs(k,t+,i+);
fa[fx]=fx;
}
dfs(k,t,i+);
}
int main()
{
qread(n);qread(m);
for(int i=;i<=m;i++){qread(a[i].x);qread(a[i].y);qread(a[i].c);}
sort(a+,a+m+,cmp);
for(int i=;i<=n;i++)fa[i]=i;
int k=,t=;memset(d,,sizeof(d));memset(s,,sizeof(s));
for(int i=;i<=m;i++)
{
int fx=findfa(a[i].x),fy=findfa(a[i].y);
if(a[i].c!=a[i-].c)s[k]=i-,k++;//记录第k种边的最后一个位置
if(fx!=fy)
{
fa[fx]=fy;
t++;d[k]++;
}
}
s[k]=m;
if(t!=n-){printf("0\n");return ;}
for(int i=;i<=n;i++)fa[i]=i;
int ans=;
for(int i=;i<=k;i++)
{
sum=;
dfs(i,,s[i-]+);
ans=(ans*sum)%mod;
for(int j=s[i-]+;j<=s[i];j++)
{
int fx=findfa(a[j].x),fy=findfa(a[j].y);
if(fx!=fy)fa[fx]=fy;
}
}
printf("%d\n",ans);
return ;
}