题目
P4208 [JSOI2008]最小生成树计数
以前一直以为JSOI的题应该比较水吧，果然还是我太ruo了
做法
两个性质
\(1.\)：最小生成树中同一权值的边数一定
\(2.\)：最小生成树中同一权值的边连接后联通块状态相同
利用这两个性质，开两个数组维护所属联通块(并查集)，每次处理同一边权的点
假设我们上一次权值的记录为\(last\)，实时更新的为\(fa\)
处理此权值边：如果在last中的两点没联通那标记一下这是可用的，让这些点形成树，存在有些在处理此边权时联通，会形成环，这些不是不能选，因为我们用的方法是分治形成树，用这些边单独形成一棵树，显然所有权值的边最后会形成一棵大树，所以我们这里记录祖先是用的联通之前的，然后更新祖先是实时更新的(可以理解为处理一个权值后就把那些缩点)
然后处理同一权值，这些块可能不止一个就分开计算这些边能形成的树，矩阵树就行了
My complete code
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<string>#include<ctime>#include<vector>using namespace std;typedef int LL;const LL maxn=200;const LL p=31011;inline LL Read(){ ???LL x(0),f(1); char c=getchar(); ???while(c<'0'||c>'9'){ ???????if(c=='-') f=-1; c=getchar(); ???} ???while(c>='0'&&c<='9') ???????x=(x<<3)+(x<<1)+c-'0',c=getchar(); ???return x*f;}struct node{ ???LL u,v,d;}e[maxn*maxn];LL n,m;LL g[maxn][maxn],D[maxn][maxn];inline bool cmp(node x,node y){ ???return x.d<y.d;}LL Get_fa(LL u,LL *fa){ ???return fa[u]=(fa[u]==u)?u:Get_fa(fa[u],fa);}inline LL Calc(LL N){ ???LL tr(0),ret(1); ???for(LL i=1;i<=N;++i){ ???????for(LL j=i+1;j<=N;++j){ ???????????while(D[j][i]){ ???????????????LL tmp=D[i][i]/D[j][i]; ???????????????for(LL k=1;k<=N;++k){ ???????????????????D[i][k]=(D[i][k]-tmp*D[j][k]%p+p)%p; ???????????????????swap(D[i][k],D[j][k]); ???????????????} ???????????????tr^=1; ???????????} ???????} ???????if(D[i][i]==0) ???????????return 0; ???????ret=ret*D[i][i]%p; ???} ???if(tr) ???????ret=p-ret; ???return ret;}LL ans=1;LL fa[maxn],last[maxn];bool visit[maxn];vector<LL> belong[maxn];inline void Solve(){ ???for(LL i=1;i<=n;++i) ???????if(visit[i]) ???????????belong[Get_fa(i,fa)].push_back(i), ???????????visit[i]=false; ???LL ret(1); ???for(LL i=1;i<=n;++i){ ???????LL size(belong[i].size()); ???????if(size<=1) ???????????continue; ???????memset(D,0,sizeof(D)); ???????for(LL j=1;j<=size;++j){ ???????????LL u(belong[i][j-1]); ???????????for(LL k=j+1;k<=size;++k){ ???????????????LL v(belong[i][k-1]); ???????????????if(g[u][v]){ ???????????????????D[j][k]=D[k][j]=(p-g[u][v])%p, ???????????????????D[j][j]+=g[u][v],D[k][k]+=g[u][v]; ???????????????} ???????????} ???????} ???????ans=(ans*Calc(size-1))%p; ???????for(LL j=1;j<=size;++j) ???????????last[belong[i][j-1]]=i; ???} ???for(LL i=1;i<=n;++i) ???????belong[i].clear(), ???????fa[i]=last[i]=Get_fa(i,last);}int main(){ ???n=Read(),m=Read(); ???for(LL i=1;i<=m;++i) ???????e[i].u=Read(),e[i].v=Read(),e[i].d=Read(); ???sort(e+1,e+1+m,cmp); ???e[0]=e[1]; ???for(LL i=1;i<=n;++i) ???????last[i]=fa[i]=i; ???for(LL i=1;i<=m;++i){ ???????if(e[i].d^e[i-1].d){ ???????????Solve(); ???????????memset(g,0,sizeof(g)); ???????} ???????LL u(e[i].u),v(e[i].v); ???????LL fu(Get_fa(u,last)),fv(Get_fa(v,last)) ; ???????if(fu^fv){ ???????????visit[fu]=visit[fv]=true; ???????????++g[fu][fv]; ++g[fv][fu]; ???????????fa[Get_fa(fu,fa)]=Get_fa(fv,fa); ???????} ???}Solve(); ???for(LL i=2;i<=n;++i) ???????if(last[i]^last[i-1]){ ???????????printf("0"); ???????????return 0; ???????} ???printf("%d",ans); ???return 0;}/**/P4208 [JSOI2008]最小生成树计数
原文地址：https://www.cnblogs.com/y2823774827y/p/10269965.html