问一个图最小生成树的个数，n<100,m<1000，规定相同权值的边不超过10条。
每天午觉起来很长一段时间都仿佛活在梦中。上午看的下午来打，狂RE不止，发现一种边只有一条的情况没有r会GG。。
//Twenty#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<queue>#include<vector>typedef long long LL;const int maxn=100+5;const int maxm=1000+5;const int mod=31011;using namespace std;int ans=1,sum,n,m,fa[maxn],ecnt,tot;struct edge{ ???int u,v,l,r,w,o; ???friend bool operator <(const edge &A,const edge &B) { ????????return A.w<B.w; ???}}e[maxm],ee[maxm];void init() { ???scanf("%d%d",&n,&m); ???for(int i=1;i<=m;i++) ????????scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); }int find(int x) {return x==fa[x]?x:find(fa[x]);}void kruskal() { ???sort(e+1,e+m+1); ???for(int i=1;i<=n;i++) fa[i]=i; ???for(int i=1;i<=m;i++) { ???????int u=e[i].u,v=e[i].v; ???????if(tot==n-1&&e[i].w!=ee[ecnt].w) break; ???????u=find(u),v=find(v); ???????if(!ecnt||e[i].w!=ee[ecnt].w) { ???????????????ee[++ecnt].l=i; ???????????????ee[ecnt].w=e[i].w; ???????} ???????ee[ecnt].r=i; ???????if(u!=v) { ??????????fa[u]=v; ??????????tot++; ??????????ee[ecnt].o++; ???????} ???}}void dfs(int id,int now,int k) { ???if(now==ee[id].r+1&&k==ee[id].o) sum++; ???if(now==ee[id].r+1) return ; ???int res=0; ???int u=find(e[now].u),v=find(e[now].v); ???if(u!=v) { ???????fa[u]=v; ???????dfs(id,now+1,k+1); ???????fa[u]=u; fa[v]=v; ???} ???dfs(id,now+1,k);}void work() { ???kruskal(); ???if(tot!=n-1) {printf("0"); return ;} ???for(int i=1;i<=n;i++) fa[i]=i; ???for(int i=1;i<=ecnt;i++) { ???????sum=0; ???????dfs(i,ee[i].l,0); ???????ans=(ans*sum)%mod; ???????for(int j=ee[i].l;j<=ee[i].r;j++) { ???????????int u=find(e[j].u),v=find(e[j].v); ???????????if(u!=v) fa[u]=v; ???????} ???} ???printf("%d\n",ans);}int main(){ ???init(); ???work(); ???return 0;}最小生成树的两个性质：
(1)不同的最小生成树中,每种权值的边出现的个数是确定的
(2)不同的生成树中,某一种权值的边连接完成后,形成的联通块状态是一样的
有了这两个性质，先跑一遍Kruskal求出最小生成树和每种权值的边分别出现的次数，因为相同权值的边很少，对于每种权值的边直接爆搜，乘法原理。
若是没有这个次数限制，就要用矩阵树定理解决。
BZOJ 1016[JSOI2008]最小生成树计数
原文地址：http://www.cnblogs.com/Achenchen/p/7581361.html