Description

求 \(n\) 个点以 \(1\) 为根的有向生成树个数。

\(1\leq n\leq 250\)

Solution

我终于会 \(\texttt{Matrix-Tree}\) 辣！！

写详解是不可能的，直接。

注意的是有向图度数矩阵是入度。

Code

#include 
    
     using namespace std;const int N = 250+5, yzh = 10007;int n, m, u, v, a[N][N];int gauss() {    int ans = 1;    for (int i = 2; i <= n; i++) {        for (int j = i+1; j <= n; j++)            while (a[j][i]) {                int t = a[i][i]/a[j][i];                for (int k = i; k <= n; k++) (a[i][k] -= a[j][k]*t%yzh) %= yzh;                swap(a[i], a[j]); ans *= -1;            }        (ans *= a[i][i]) %= yzh;    }    return (ans+yzh)%yzh;}void work() {    scanf("%d%d", &n, &m);    for (int i = 1; i <= m; i++) {        scanf("%d%d", &v, &u);        ++a[v][v], --a[u][v];    }    printf("%d\n", gauss());}int main() {work(); return 0; }