Description
题库链接 https://www.lydsy.com/JudgeOnline/problem.php?id=5297
求 \(n\) 个点以 \(1\) 为根的有向生成树个数.
- \(1\leq n\leq 250\)
- Solution
我终于会 \(\texttt{Matrix-Tree}\) 辣!!
写详解是不可能的, 直接丢链接 https://www.cnblogs.com/zj75211/p/8039443.html .
注意的是有向图度数矩阵是入度.
- Code
- #include <bits/stdc++.h>
- 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; }
[CQOI 2018] 社交网络
来源: http://www.bubuko.com/infodetail-2585269.html