1016: [JSOI2008]最小生成树计数
题目：传送门
题解：
神题神题%%%
据说最小生成树有两个神奇的定理：
1、权值相等的边在不同方案数中边数相等
就是说如果一种方案中权值为1的边有n条
那么在另一种方案中权值为1的边也一定有n条
2、如果边权为1的边连接的点是x1,x2,x3
那么另一种方案中边权为1的边连接的也一定是x1,x2,x3
如果知道了这两条定理那就很好做了啊：
因为等权边的条数一定，那么我们就可以预处理求出不同边权的边的条数
题目很人道的保证了边权相同的边不会超过10条，那就可以光明正大的递归得出方案数了啊
接下来就要利用定理2了：
因为连接的点总是不变的，所以每一次选边是没有影响的，那么递归求出每一种权值边的方案数之后用乘法原理乘起来就ok
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cmath> 5 #include<algorithm> 6 #define mod 31011 7 #define qread(x) x=read() 8 using namespace std; 9 inline int read()10 {11 ????int f=1,x=0;char ch;12 ????while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 ????while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14 ????return f*x;15 }16 struct node17 {18 ????int x,y,c,next;19 }a[1100];int n,m,sum;20 int fa[110];21 int findfa(int x)22 {23 ????if(x==fa[x])return x;24 ????return findfa(fa[x]);25 }26 bool cmp(node n1,node n2)27 {28 ????return n1.c<n2.c;29 }30 int d[1100],s[1100];31 void dfs(int k,int t,int i)//当前选的是第k种边，已经选了t条，当前位置为第i条边 32 {33 ????if(i==s[k]+1)34 ????{ 35 ????????if(t==d[k])36 ????????????sum++,sum%=mod;37 ????????return ;38 ????}39 ????int fx=findfa(a[i].x),fy=findfa(a[i].y);40 ????if(fx!=fy)41 ????{42 ????????fa[fx]=fy;43 ????????dfs(k,t+1,i+1);44 ????????fa[fx]=fx;45 ????}46 ????dfs(k,t,i+1);47 }48 int main()49 {50 ????qread(n);qread(m);51 ????for(int i=1;i<=m;i++){qread(a[i].x);qread(a[i].y);qread(a[i].c);}52 ????sort(a+1,a+m+1,cmp);53 ????for(int i=1;i<=n;i++)fa[i]=i;54 ????int k=1,t=0;memset(d,0,sizeof(d));memset(s,0,sizeof(s));55 ????for(int i=1;i<=m;i++)56 ????{57 ????????int fx=findfa(a[i].x),fy=findfa(a[i].y);58 ????????if(a[i].c!=a[i-1].c)s[k]=i-1,k++;//记录第k种边的最后一个位置 59 ????????if(fx!=fy)60 ????????{61 ????????????fa[fx]=fy;62 ????????????t++;d[k]++;63 ????????}64 ????}65 ????s[k]=m;66 ????if(t!=n-1){printf("0\n");return 0;}67 ????for(int i=1;i<=n;i++)fa[i]=i;68 ????int ans=1;69 ????for(int i=1;i<=k;i++)70 ????{71 ????????sum=0;72 ????????dfs(i,0,s[i-1]+1);73 ????????ans=(ans*sum)%mod;74 ????????for(int j=s[i-1]+1;j<=s[i];j++)75 ????????{76 ????????????int fx=findfa(a[j].x),fy=findfa(a[j].y);77 ????????????if(fx!=fy)fa[fx]=fy;78 ????????}79 ????}80 ????printf("%d\n",ans);81 ????return 0;82 }bzoj1016: [JSOI2008]最小生成树计数(kruskal+dfs)
原文地址：https://www.cnblogs.com/CHerish_OI/p/8157278.html