BZOJ 1016: [JSOI2008]最小生成树计数

求一个无向图(n,m)的生成树数可以构造下面一个矩阵
矩阵大小:(n * n)
对于一个位置(i,j)
如果i==j则上面的数为点i的度数
否则为i到j的边数的相反数
如一个图1<->2,2<->3点数为3
则矩阵为
1 -1 0
-1 2 -1
0 -1 1
吧这个矩阵的第i行和第i列去掉(1<=i<=n i取任意值都可) 然后叫这个剩下来的矩阵n-1阶余子式 求这个矩阵的行列式的绝对值即为该图的生成树数 (我不知道行列式是什么啊QAQ 我就只知道能这么用QvQ 虽然听起来不像是一个值 但是就这么用吧QvQ) 求一个矩阵的行列式就是先用高斯消元把这个矩阵消成上三角矩阵 然后ans=π(f[i][i]) 对于求生成树数这个矩阵 ans最后会是一个整数 但是中间步骤可能是小数 最小生成树计数怎么做呢=、= 先把边按权值从小到大排序 从小到大遍历 对于边权相同的一些边取出来 对于这些边的每个联通子图求生成树数(自环要无视) ans=π每个联通子图求生成树数 最后把每个联通块用并查集分别并为一个点 然后再做下一个边权的边集即可 这题的ans可能很大 如果直接开double或long double都可能爆(其实long double不会=-=) 这题有mod一个数 如果可以让ans中间过程也是整数就非常好 考虑对一个矩阵的某行减掉某行的某倍 这个矩阵的行列式是不会变的 则我们可以用一个类似辗转相除的方法 让这个矩阵在保证每个元素仍是整数的情况下变为上三角矩阵(详见代码) 【周冬《生成树的计数及其应用》】

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll inf = 31011;
const ll maxn = 105;

struct lin
{
    ll fr, to, v;
}p[10005];

struct line
{
    ll next, to;
}li[10005];

ll be[maxn], fa[maxn], l, to[maxn], tot, ans, n, m;
ll v[maxn][maxn];
queue<ll> q;

bool cmp(lin a, lin b)
{
    return a.v < b.v;
}

void makeline(ll fr, ll to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

ll bfs(ll now)
{
    for (to[now] = tot = 1, v[1][1] = 0, q.push(now); !q.empty(); )
    {
        ll now = q.front();
        q.pop();
        for (ll i = be[now]; i; i = li[i].next)
        {
            ll _to = li[i].to;
            if (_to == now) continue;
            if (!to[_to])
            {
                to[_to] = ++tot;
                for (ll j = 1; j <= tot; ++j)
                    v[j][tot] = v[tot][j] = 0;
                q.push(_to);
            }
            v[to[now]][to[now]] += 1;
            v[to[now]][to[_to]] -= 1;
        }
    }
    if (tot == 1) return 1;
    ll ans = 1;
    for (ll i = 1; i < tot; ++i)
    {
        if (!v[i][i])
        {
            ll ans = -1;
            for (ll j = i + 1; j < tot; ++j)
                if (ans == -1 || abs(v[j][i]) > abs(v[ans][i]))
                    ans = j;
            for (ll j = i; j < tot; ++j)
                swap(v[i][j], v[ans][j]);
        }
        for (ll j = i + 1; j < tot; ++j)
            while (v[j][i])
            {
                ll t = v[i][i] / v[j][i];
                for (ll k = i; k < tot; ++k)
                    v[i][k] -= t * v[j][k],
                    swap(v[j][k], v[i][k]);
            }
        ans = (ans * v[i][i]) % inf;
    }
    return ans % inf;
}

ll getfa(ll now)
{
    return (!fa[now]) ? now : fa[now] = getfa(fa[now]);
}

int main()
{
    ans = 1;
    scanf("%lld%lld", &n, &m);
    for (ll i = 0; i < m; ++i)
        scanf("%lld%lld%lld", &p[i].fr, &p[i].to, &p[i].v);
    sort(p, p + m, cmp);
    ans = 1;
    for (ll i = 0; i < m;)
    {
        l = 0;
        memset(be, 0, sizeof(be));
        memset(to, 0, sizeof(to));
        ll j;
        for (j = i; j < m && p[i].v == p[j].v; ++j)
            makeline(getfa(p[j].fr), getfa(p[j].to)),
            makeline(getfa(p[j].to), getfa(p[j].fr));
        ll t = j;
        for (ll j = 1; j <= n; ++j)
            if (!to[getfa(j)])
                ans = (ans * bfs(getfa(j))) % inf;
        for (ll j = i; j < t; ++j)
            if (getfa(p[j].fr) != getfa(p[j].to))
                fa[getfa(p[j].fr)] = getfa(p[j].to);
        i = t;
    }
    for (int i = 1; i <= n; ++i)
        if (getfa(i) != getfa(1))
        {
            cout << 0;
            return 0;
        }
    cout << abs(ans);
}