UVA10766-Organising the Organisation（生成树计数+Matrix-tree定理）

119 阅读 0 评论 79 点赞

我是靠谱客的博主成就过客，这篇文章主要介绍UVA10766-Organising the Organisation（生成树计数+Matrix-tree定理），现在分享给大家，希望可以做个参考。

题目链接

http://acm.hust.edu.cn/vjudge/contest/67265#problem/I

题意

给定一张图，并且确定根节点，求生成树的个数

思路

因为是无向图，所以哪个节点作为根节点都没有影响，因此题目转化为无向图的生成树计数
Matrix-tree定理：
对于图G，设D[G]为G的度数矩阵，A[G]为G的邻接矩阵，则C[G] = D[G] - A[G]；并且生成树的个数 = C[G]的任意一个n - 1阶主子式的行列式
因此只需要求出行列式即可
求行列式采用消元法（还没有弄清楚为什么用long double会WA）

代码

复制代码

#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>
using namespace std;

#define PI acos(-1.0)
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define mp make_pair
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "wb", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) cout << #x << " = " << x << endl
#define lc o << 1
#define rc o << 1 | 1
#define pl() cout << endl
#define CLR(a, x) memset(a, x, sizeof(a))
#define FILL(a, n, x) for (int i = 0; i < n; i++) a[i] = x

const int maxn = 55;
int n, m, k;
LL C[maxn][maxn], A[maxn][maxn];

LL det(LL a[][maxn], int n) {
    int i, j, k, r;
    LL res = 1;
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            while (a[j][i]) {
                LL f = a[i][i] / a[j][i];
                for (int k = i; k < n; k++) a[i][k] -= f * a[j][k];
                for (int k = i; k < n; k++) swap(a[i][k], a[j][k]);
                res = -res;
            }
        }
        if (a[i][i] == 0) return 0;
        res *= a[i][i];
    }
    return res < 0 ? -res : res;
}

void init() {
    memset(C, 0, sizeof(C));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            A[i][j] = 1;
        }
    }
}

int main() {
    while (~scan3(n, m, k)) {
        init();
        for (int i = 0; i < m; i++) {
            int x, y;
            scan2(x, y);
            x--; y--;
            A[x][y] = A[y][x] = 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && A[i][j]) {
                    C[i][i]++;
                    C[i][j] = -1;
                }
            }
        }
        LL ans = det(C, n - 1);
        printf("%lldn", ans);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>
using namespace std;

#define PI acos(-1.0)
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define mp make_pair
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "wb", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) cout << #x << " = " << x << endl
#define lc o << 1
#define rc o << 1 | 1
#define pl() cout << endl
#define CLR(a, x) memset(a, x, sizeof(a))
#define FILL(a, n, x) for (int i = 0; i < n; i++) a[i] = x

const int maxn = 55;
int n, m, k;
LL C[maxn][maxn], A[maxn][maxn];

LL det(LL a[][maxn], int n) {
    int i, j, k, r;
    LL res = 1;
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            while (a[j][i]) {
                LL f = a[i][i] / a[j][i];
                for (int k = i; k < n; k++) a[i][k] -= f * a[j][k];
                for (int k = i; k < n; k++) swap(a[i][k], a[j][k]);
                res = -res;
            }
        }
        if (a[i][i] == 0) return 0;
        res *= a[i][i];
    }
    return res < 0 ? -res : res;
}

void init() {
    memset(C, 0, sizeof(C));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            A[i][j] = 1;
        }
    }
}

int main() {
    while (~scan3(n, m, k)) {
        init();
        for (int i = 0; i < m; i++) {
            int x, y;
            scan2(x, y);
            x--; y--;
            A[x][y] = A[y][x] = 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && A[i][j]) {
                    C[i][i]++;
                    C[i][j] = -1;
                }
            }
        }
        LL ans = det(C, n - 1);
        printf("%lldn", ans);
    }
    return 0;
}