「JSOI2008」最小生成树计数 题解报告

简要题意

现在给出了一个简单无向加权图。你希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。输出方案数对\(31011\)取模。

SOLUTION

这个题求最小生成树的方案

所以我们从最小生成树入手

（根据kruskal的思路）

我们可以知道 同一个图的每个最小生成树中，边权相等的边数量相等。

感性理解：然后由于要求的是最小生成树的方案

所以对于树边，我们只能用同样权值去替代ta

否则就不是最小生成树的值

我们考虑枚举边权

每次根据剩下树边缩点（其实就是将点连上了，方便处理）

得到一张新的DAG，

我们只是要考虑边权相等的边对于新图生成树的方案数

因此我们可以做矩阵树

最后的答案就是所有的乘积

注意：

这个题模数P不是质数

因此不能用逆元求det值

CODE

const int N=1e2+2,M=1e3+2,P=31011;//不是质数 
struct node{ll x,y,w;}t[M],s[M];
vector<node> G[M]; 
bool operator<(node a,node b){
    return a.w<b.w;
}
ll is[M],fa[N],c[N],n,D[N][N],A[N][N],C[N][N]; 
ll find(ll x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%P;
        a=a*a%P; 
		b>>=1;
    }
    return res%P;
}
ll det(ll n){
	ll ans=1;
	for(ll i=1;i<n;i++){
		for(ll j=i+1;j<=n;j++){ 
			while(C[j][i]){ 
				ll l=C[i][i]/C[j][i];//l表示辗转相减的次数
				for(ll k=1;k<=n;k++){
					C[i][k]=(C[i][k]-C[j][k]*l%P+P)%P; 
				} 
			 	for(ll k=1;k<=n;k++){
			 		swap(C[i][k],C[j][k]);
			 	}//交换两列位置取相反数
			 	ans*=-1;//相反数
		 	}
		}
	}
	for(ll i=1;i<=n;i++){
		ans=(ans*C[i][i]%P+P)%P;
	}//此时已经削减为上三角矩阵，所以直接求对角线元素之积就可以了
	return ans;
}
int main(){
    ll n,m,all=0,tmp=0,cnt=0;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++) fa[i]=i;
    for(ll i=1;i<=m;i++){
    	scanf("%lld%lld%lld",&t[i].x,&t[i].y,&t[i].w);
    }
    sort(t+1,t+m+1);
    //kruskal 
    for(ll i=1;i<=m;i++){
    	ll x=t[i].x,y=t[i].y,w=t[i].w;
        if(w!=tmp) all++,tmp=w;
        G[all].push_back(t[i]);
        if(find(x)==find(y))continue;
        fa[find(x)]=find(y);
        is[all]=1;
		s[++cnt]=t[i];
		s[cnt].w=all;
    }
    if(cnt!=n-1){
        printf("0");
        return 0;
    } 
    ll ans=1;
    for(ll i=1;i<=all;i++){
        if(!is[i]) continue;//如果最小生成树中没有用到此边权 
		for(ll i=1;i<=n;i++) fa[i]=i;
		ll tot=0;
		for(ll j=1;j<=cnt;j++){		//将生成树上的边全部连上并缩点
			ll x=s[j].x,y=s[j].y,w=s[j].w;
			if(w==i) continue;
			if(find(x)==find(y))continue;
			fa[find(x)]=find(y);
		}
		for(ll j=1;j<=n;j++){
			if(fa[j]==j) c[j]=++tot;
		}
		for(ll j=1;j<=n;j++){
			c[j]=c[find(j)];
		}
        for(auto j:G[i]){//将原图中此边权的边全部连上 
            ll x=c[j.x],y=c[j.y];
            D[x][x]++,D[y][y]++;
            A[x][y]++,A[y][x]++;
        }
        for(ll j=1;j<=tot;j++){
        	for(ll k=1;k<=tot;k++){
        		C[j][k]=(D[j][k]-A[j][k]+P)%P;
        	}
        }
        ans=ans*det(tot-1)%P;
        for(auto j:G[i]){ //删除连上的边 
            ll x=c[j.x],y=c[j.y];
            D[x][x]--,D[y][y]--;
            A[x][y]--,A[y][x]--;
        }
    }
    printf("%lld",ans);
    return 0;
}

完结撒花❀