OJ题号：

　　BZOJ1016

题目大意：

　　给定一个无向带权图，求最小生成树的个数。

思路：

　　先跑一遍最小生成树，统计相同权值的边出现的个数。

　　易证不同的最小生成树，它们不同的那一部分边的权值实际上是相同的。

　　所以我们可以暴力枚举相同权值的边，统计加入这些边总共能有多少种方法。

　　根据乘法原理，把每种边的方法数乘起来即可。

　　然后就O(2^n)暴力水过这道题。

　　实际上用Matrix-Tree可以做到O(n^3)。

1 */  2 #include
     
        3 #include
      
         4 #include
       
          5 #include
        
           6   7 inline int getint() {  8     register char ch;  9     while(!isdigit(ch=getchar())); 10     register int x=ch^'0'; 11     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 12     return x; 13 } 14 const int mod=31011; 15 const int V=101; 16  17 struct Edge1 { 18     int u,v,w; 19     bool operator < (const Edge1 &another) const { 20         return w
         
           e1; 24  25 struct Edge { 26     int to,w; 27 }; 28 std::vector
          
            e[V]; 29 inline void add_edge(const int &u,const int &v,const int &w) { 30 e[u].push_back((Edge){v,w}); 31 } 32 33 struct DisjointSet { 34 int anc[V],cnt; 35 int find(const int &x) const { 36 return x==anc[x]?x:find(anc[x]); 37 } 38 void reset(const int &n) { 39 cnt=n; 40 for(register int i=1;i<=n;i++) { 41 anc[i]=i; 42 } 43 } 44 void Union(const int &x,const int &y) { 45 anc[find(x)]=find(y); 46 cnt--; 47 } 48 bool isConnected(const int &x,const int &y) const { 49 return find(x)==find(y); 50 } 51 int stat() const { 52 return cnt; 53 } 54 }; 55 DisjointSet s; 56 57 struct Hash { 58 unsigned l,r; 59 int v; 60 }; 61 std::vector
           
             a; 62 63 inline void kruskal() { 64 std::sort(e1.begin(),e1.end()); 65 for(register unsigned i=0;i
            
             a[in].r) { 85 if(d==a[in].v) tmp++; 86 return; 87 } 88 const int &u=e1[x].u,&v=e1[x].v; 89 const int p=s.find(u),q=s.find(v); 90 if(p!=q) { 91 s.anc[p]=q; 92 dfs(in,x+1,d+1); 93 s.anc[p]=p; 94 s.anc[q]=q; 95 } 96 dfs(in,x+1,d); 97 } 98 99 int main() {100 int n=getint();101 for(register int m=getint();m;m--) {102 const int u=getint(),v=getint(),w=getint();103 e1.push_back((Edge1){u,v,w});104 }105 s.reset(n);106 kruskal();107 if(s.stat()!=1) {108 puts("0");109 return 0;110 }111 s.reset(n);112 int ans=1;113 for(register unsigned i=0;i