bzoj1016/luogu4208 最小生成树计数 (kruskal+暴搜)

由于有相同权值的边不超过10条的限制，所以可以暴搜

先做一遍kruskal，记录下来每个权值的边使用的数量（可以离散化一下）

可以证明，对于每个权值，所有的最小生成树中选择的数量是一样的、而且它们连成的连通块也是一样的

所以我们把每个权值的边分开暴搜所有可能的情况，最后再乘到一起就是答案

 #include<bits/stdc++.h>

 #define pa pair<int,int>

 #define CLR(a,x) memset(a,x,sizeof(a))

 using namespace std;

 typedef long long ll;

 const int maxn=,maxm=,P=;

 inline ll rd(){

     ll x=;char c=getchar();int neg=;

     while(c<''||c>''){if(c=='-') neg=-;c=getchar();}

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x*neg;

 }

 struct Edge{

     int a,b;

     ll l;

 }eg[maxm];

 int egh[maxn],ect;

 int N,M,L,cnt[maxm];

 int fa[maxn],ans,sum;

 inline bool cmp(Edge a,Edge b){return a.l<b.l;}

 inline int getf(int x){

     while(x!=fa[x]) x=fa[x];return x;

 }

 void dfs(int x,int y,int n){

     if(x>M||eg[x].l!=y){

         if(n==cnt[y]) sum=(sum+)%P;

         return;

     }

     int aa=getf(eg[x].a),bb=getf(eg[x].b);

     if(aa!=bb){

         fa[aa]=bb;

         dfs(x+,y,n+);

         fa[aa]=aa;

     }

     dfs(x+,y,n);

 }

 int main(){

     //freopen("","r",stdin);

     int i,j,k;

     N=rd(),M=rd();

     for(i=;i<=M;i++){

         eg[i].a=rd(),eg[i].b=rd();

         eg[i].l=rd();

     }sort(eg+,eg+M+,cmp);

     int lst=-;

     for(i=,j=;i<=M;i++){

         if(eg[i].l!=lst) j++;

         lst=eg[i].l,eg[i].l=j;

     }

     for(i=;i<=N;i++) fa[i]=i;

     for(i=,j=;i<=M;i++){

         int x=getf(eg[i].a),y=getf(eg[i].b);

         if(x!=y){

             fa[x]=y;

             j++;cnt[eg[i].l]++;

         }

     }

     if(j<N-){printf("0\n");return ;}

     for(i=;i<=N;i++) fa[i]=i;

     int ans=;

     for(i=,j=;i<=M;i++){

         if(eg[i].l!=eg[i-].l){

             sum=;dfs(i,eg[i].l,);

             ans=(ans*sum)%P;

         }

         int x=getf(eg[i].a),y=getf(eg[i].b);

         if(x!=y){

             fa[x]=y;j++;

         }

     }

     printf("%d\n",ans);

     return ;

 }