[CQOI2018]社交网络
题目链接
一句话题意：给定n个点m条有向边，求以1号点为根的树形图数量。
solution：构造有向图基尔霍夫矩阵，求出det(M[1][1])
证明有向图的矩阵树定理：
思路和证明无向图的差不多，构造辅助矩阵。
构造两个矩阵A和B，每列代表一条边x->y。
在A的一列中，第x行为-1，第y行为1，其余是0
在B的一列中，第y行为1，其余为0
A就是按照边的方向定正负的无向图正常的辅助矩阵
B我们把它叫做入度矩阵
这样A*B(T)是基尔霍夫矩阵C：
Cij是A的第i行 点乘 B的第i行
i=j时当且仅当边是x->i才有贡献，并且贡献都是1
i!=j时只有i->j时才是-1，否则都是0
设A'为A去掉第1行选n-1列，B'同理
考虑和无向图一样柯西比内，这样相当于选出了n-1条有向边
现在我们考虑哪一些情况可以对最后答案产生贡献。
考虑det(A')=0可以排除掉有环的情况(包括了两点间有两个方向的边)
现在不考虑边的方向的话，剩下有可能做出贡献的是棵树
我们先证 a.当且仅当这是个树形图，且以1为根时det(B')!=0
再证 b.符合这样的情况时det(A')det(B')=1
这样最后的答案就是以1为根的树形图计数了
a.
首先以i为根的树形图相当于i的入度为0，其他每个点入度为1
现在B矩阵中有除1外的n-1个点，有n-1条边对应n-1个列向量，每个有一行为-1
-
如果1号点的入度>0，剩下只有n-2个不为0的数，而B'是个大小为n-1的方阵，行列式的每项需要n-1个数，故det(B')=0
-
1号点的入度为0时，只有1号点可能成为树形图的根，只需要判断是否是树形图。剩下n-1个入度分配给n-1个点，如果不是每个点一个度数，抽屉原理有一个点p入度>=2，B矩阵中对应的两个列向量相同，det(B’)=0
结论：当且仅当它是个以1为根的树形图时，det(A')det(B')!=0
b.
法一：
从叶子往上处理，考虑x->y->z
把x->y的列向量*-1，（也就是第y行为1）
加到y->z的列向量上，把它变成y=1,z=-1
我们发现它把叶节点变成了跟A矩阵一样的形式，行列式的值并没有变
然后一直这样处理直到A'=B',
我们发现自己证出了det(A')=det(B')
所以平方一下det(A')det(B')=1
法二：
显然有det(B')=det(I)=1
按照无向图的方法求det(A')，不需要改边的方向，那么显然det(A')=det(I)=1
复述一下证明过程，从叶子到根处理形如x->y->z的边
把x->y加到y->z上，变成x->y,x->z，此时det不变
最后每条边会变成1->z,而第一行已经被删掉了
剩下的是个单位矩阵，即det(A')=det(I)=1
结论：当它是个以1为根的树形图时，det(A')det(B')=1,否则=0
证明如果有不对的地方请联系我，谢谢~