bzoj 4596: [Shoi2016]黑暗前的幻想乡 （矩阵树定理+容斥原理）

题目描述

传送门

题目大意：n个点要修n-1条路（形成一棵树）。有n-1个公司，每个公司可以修建某些路径。求每个公司恰好修建一条路的方案数。

题解

生成树计数一般都是用基尔霍夫矩阵求行列式来做，关键是怎么解决每个公司恰好修建一条路的限制。 根据容斥原理答案就是：至少0个公司没有修路的方案-至少1个公司没有修路的方案+至少2个公司没有修路的方案……

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 20 #define LL long long #define p 1000000007 using namespace std; LL a[N][N]; int n,m,tot,nxt[10003],point[10003],u[10003],v[10003]; void add(int x,int y,int z) { tot++; nxt[tot]=point[x]; point[x]=tot; u[tot]=y; v[tot]=z; } LL guass(int n) { for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=(a[i][j]%p+p)%p; int num; int mark=0; for (int i=1;i<=n;i++) { num=i; for (int j=i+1;j<=n;j++) if (abs(a[j][i])>abs(a[num][i])) num=j; if (num!=i) mark^=1; for (int j=1;j<=n;j++) swap(a[i][j],a[num][j]); for (int j=i+1;j<=n;j++) while (a[j][i]!=0) { LL tmp=a[j][i]/a[i][i]; for (int k=1;k<=n;k++) a[j][k]=(a[j][k]+p-tmp*a[i][k]%p)%p; if (!a[j][i]) break; mark^=1; for (int k=1;k<=n;k++) swap(a[j][k],a[i][k]); } } LL ans=1; if (mark) ans=-ans; for (int i=1;i<=n;i++) ans=(ans*a[i][i])%p; ans=(ans%p+p)%p; return ans; } int main() { freopen("a.in","r",stdin); scanf("%d",&n); int n1=n-1; for (int i=0;i<n1;i++) { scanf("%d",&m); int x,y; for (int j=1;j<=m;j++) { scanf("%d%d",&x,&y); add(i,x,y); } } LL ans=0; for (int i=0;i<(1<<n1);i++) { memset(a,0,sizeof(a)); int cnt=0; for (int j=0;j<n1;j++) if ((i>>j)&1) { for (int k=point[j];k;k=nxt[k]) { //cout<<u[k]<<" "<<v[k]<<endl; a[u[k]][v[k]]--; a[v[k]][u[k]]--; a[u[k]][u[k]]++; a[v[k]][v[k]]++; } cnt++; } LL t=guass(n1); cnt=n1-cnt; if (cnt&1) ans=(ans-t+p)%p; else ans=(ans+t)%p; } printf("%lld\n",ans); }