洛谷 P4336 [SHOI2016]黑暗前的幻想乡 题解【矩阵树定理】【容斥】
点击量：35
矩阵树定理明明只是个记结论的东西对吧..（大雾
题目描述
四年一度的幻想乡大选开始了，最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡，扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪（人类）博丽灵梦和八云紫等人整日高谈所有妖怪平等，幻想乡多元化等等，对于幻想乡目前面临的种种大问题却给不出合理的解决方案。
风见幽香是幻想乡里少有的意识到了问题严重性的大妖怪。她这次勇敢地站了出来参加幻想乡大选，提出包括在幻想乡边境建墙（并让人类出钱），大力开展基础设施建设挽回失业率等一系列方案，成为了大选年出人意料的黑马并顺利地当上了幻想乡的大统领。
幽香上台以后，第一项措施就是要修建幻想乡的公路。幻想乡一共有 $n$ 个城市，之前原来没有任何路。幽香向选民承诺要减税，所以她打算只修 $n- 1$ 条公路将这些城市连接起来。但是幻想乡有正好 $n-1$ 个建筑公司，每个建筑公司都想在修路地过程中获得一些好处。虽然这些建筑公司在选举前没有给幽香钱，幽香还是打算和他们搞好关系，因为她还指望他们帮她建墙。所以她打算让每个建筑公司都负责一条路来修。
每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所以幽香打算 $n-1$ 条能够连接幻想乡所有城市的边，然后每条边都交给一个能够负责该边的建筑公司修建，并且每个建筑公司都恰好修建一条边。
幽香现在想要知道一共有多少种可能的方案呢？两个方案不同当且仅当它们要么修的边的集合不同，要么边的分配方式不同。
输入格式
第一行包含一个整数 $n$，表示城市个数。
接下来 $n-1$ 行，第 $i$ 行表示第 $i$ 个建筑公司可以修建的路的列表：以一个非负数 $m_i$ 开头，表示其可以修建 $m_i$ 条路；接下来有 $m_i$ 对数，每对数表示一条边的两个端点。其中不会出现重复的边，也不会出现自环。
输出格式
输出一行一个整数，表示所有可能的方案数对 $10^9+7$ 取模的结果。
样例 1 输入
4 2 3 2 4 2 5 2 1 3 1 3 2 4 1 4 3 4 2 1 3 2 4 1 4 2样例输出
17数据范围与约定
Case # $n$ $1,2$ $\leq 5$ $3\sim 5$ $\leq 8$ $6$ $\leq 10$ $7\sim 10$ $\leq 17$
题解：
矩阵树定理学习资料：[学习笔记]高斯消元、行列式、Matrix-Tree 矩阵树定理 by xyz32768
首先介绍矩阵树定理的结论：
给定图 $G=\langle V,E\rangle$。令 $D$ 是图 $G$ 的度数矩阵，$D[i,i]$ 为点 $i$ 的度数，其余位置为 $0$。
令 $A$ 是图 $G$ 的邻接矩阵，$A[u,v]=A[v,u]$ 表示 $(u,v)$ 之间的直接边数。$D,A$ 的大小都是 $V\times V$。
$K$ 是图 $G$ 的基尔霍夫矩阵，$K=D-A$。则图 $G$ 的生成树个数就是矩阵 $K$ 同时去掉第 $i$ 行第 $i$ 列所得到的矩阵 $K’$ 的行列式（$i$ 任选）。$K’$ 的大小就是 $(V-1)\times(V-1)$
行列式有一种求法就是把 $K’$ 化为上三角矩阵。也就是通过行列之间的加减，使得 $K’$ 的第 $i$ 行前 $i-1$ 个位置都是 $0$。
这一过程不能对原来的某一行乘除 $k$，但是可以对某一行加上另一行的 $k$ 倍。当拿第 $i$ 行去消第 $j$ 行第 $i$ 列时，不是把 $K'[i,i]$ 化为 $1$，而是拿用 $K'[j]$ 减去 $K'[i]$ 的 $\frac{K'[j,i]}{K'[i,i]}$ 倍。
当没有逆元时可以用辗转相除来消掉第 $j$ 行第 $i$ 列。
然后 $\prod_{i=1}^{V-1}K'[i,i]$ 就是行列式了。
对于行列式的本质先把坑留着，看懂了再开坑。
矩阵树定理是用来求一个无向图的生成树个数的，接下来考虑每个公司恰好负责一条边。
如果不限制公司，就是对输入的 $\sum_{i=1}^{n-1}m_i$ 条边求生成树个数。此时的生成树会出现一个公司负责两条边的情况，但是正确答案也一定包含在这些生成树里。
考虑容斥。当删掉一个公司能负责的边时，方案中就没有正确答案了。因为生成树中有 $n-1$ 条边，恰好要由 $n-1$ 个公司负责，而此时只有 $n-2$ 个公司，由鸽笼原理，至少有一个公司要负责两条边。
由这个“至少”考虑到不限制公司的情况，就是至少有零个公司要负责两条边。
令 $S\subseteq\{1,2,\ldots,n-1\}$，记只选择 $S$ 集合内的公司负责的边计算生成树的个数为 $f(S)$。则答案为 $\sum_{S\subseteq\{1,2,\ldots,n-1\}}(-1)^{n-1-|S|}f(S)$。
然后枚举 $S$ 即可。
时间复杂度为 $O(2^n\cdot n^3\log n)$。
Code：
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define p 1000000007
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
int read()
{
int x=0;
char ch=gc();
while(ch<'0'||ch>'9')
ch=gc();
while(ch>='0'&&ch<='9')
{
x=x*10+(ch&15);
ch=gc();
}
return x;
}
int f[20][20];
vector<pair<int,int> > c[20];
int calc(int n)
{
bool re=0;
for(int i=1;i<=n;++i)
{
for(int j=i+1;j<=n;++j)
if(f[j][i])
{
swap(f[i],f[j]);
re^=1;
}
for(int j=i+1;j<=n;++j)
while(f[j][i])
{
swap(f[i],f[j]);
re^=1;
long long t=f[j][i]/f[i][i];
for(int k=i;k<=n;++k)
f[j][k]=(f[j][k]+p-t*f[i][k]%p)%p;
}
}
long long ans=1;
for(int i=1;i<=n;++i)
ans=ans*f[i][i]%p;
return re?(p-ans)%p:ans;
}
void add(int u,int v)
{
++f[u][u];
++f[v][v];
f[u][v]=(f[u][v]+p-1)%p;
f[v][u]=(f[v][u]+p-1)%p;
}
int main()
{
#ifdef wjyyy
freopen("a.in","r",stdin);
#endif
int n=read();
for(int i=0;i<n-1;++i)
{
int m=read();
for(int j=1;j<=m;++j)
c[i].push_back(make_pair(read(),read()));
}
int ans=0;
for(int i=1;i<(1<<(n-1));++i)
{
memset(f,0,sizeof(f));
int cnt=0;
for(int j=0;j<n-1;++j)
if((i>>j)&1)
{
++cnt;
for(vector<pair<int,int> >::iterator it=c[j].begin();it!=c[j].end();++it)
add(it->first,it->second);
}
if((cnt&1)==((n-1)&1))
ans=(ans+calc(n-1))%p;
else
ans=(ans+p-calc(n-1))%p;
}
printf("%d\n",ans);
return 0;
printf("%d\n",ans);
return 0;
}
说点什么