[JSOI2008] 最小生成树计数

根据最小生成树的一些性质,不同的最小生成树固定权值的边数是一样的
而且我们发现这题同权的边数<=10
于是可以预处理出每种权值需要多少条边,然后爆搜
然后不能路径压缩,不然你怎么回溯...
注意到n只有100,暴力并查集搜根没有任何问题
复杂度:\(O(\)边权数\(×2^{10})\),最坏也就是\(100×1024\)

#include<bits/stdc++.h>using namespace std;const int N=105,M=1005,p=31011;int re(){ ???int x=0,w=1;char ch=getchar(); ???while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} ???while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); ???return x*w;}int n,m,tot,cnt,sum,ans=1,fa[N],l[M],r[M],t[M];struct edge{int u,v,w;}E[M];bool cmp(edge a,edge b){return a.w<b.w;}int find(int x){return x==fa[x]?x:find(fa[x]);}void dfs(int x,int id,int k){ ???if(id==r[x]+1){if(k==t[x])sum++;return;} ???int fx=find(E[id].u),fy=find(E[id].v); ???if(fx^fy){fa[fx]=fy;dfs(x,id+1,k+1);fa[fx]=fx;} ???dfs(x,id+1,k);}int main(){ ???n=re(),m=re(); ???for(int i=1;i<=m;i++){ ???????E[i].u=re();E[i].v=re();E[i].w=re(); ???} ???sort(E+1,E+m+1,cmp); ???for(int i=1;i<=n;i++)fa[i]=i; ???for(int i=1;i<=m;i++){ ???????int x=find(E[i].u),y=find(E[i].v); ???????if(E[i].w^E[i-1].w){r[tot]=i-1;l[++tot]=i;} ???????if(x^y){fa[x]=y;t[tot]++;++cnt;} ???} ???r[tot]=m;if(cnt<n-1){puts("0");return 0;} ???for(int i=1;i<=n;i++)fa[i]=i; ???for(int i=1;i<=tot;i++){ ???????sum=0;dfs(i,l[i],0);ans=ans*sum%p; ???????for(int j=l[i];j<=r[i];j++){ ???????????int x=find(E[j].u),y=find(E[j].v); ???????????if(x^y)fa[x]=y; ???????} ???} ???printf("%d\n",ans);return 0;}

[JSOI2008] 最小生成树计数

原文地址：https://www.cnblogs.com/sdzwyq/p/9845790.html