HDU4408 (最小生成树计数)

Problem Description

XXX is very interested in algorithm. After learning the Prim algorithm and Kruskal algorithm of minimum spanning tree, XXX finds that there might be multiple solutions. Given an undirected weighted graph with n (1<=n<=100) vertexes and m (0<=m<=1000) edges, he wants to know the number of minimum spanning trees in the graph.

Input

There are no more than 15 cases. The input ends by 0 0 0.
For each case, the first line begins with three integers — the above mentioned n, m, and p. The meaning of p will be explained later. Each the following m lines contains three integers u, v, w (1<=w<=10), which describes that there is an edge weighted w between vertex u and vertex v( all vertex are numbered for 1 to n) . It is guaranteed that there are no multiple edges and no loops in the graph.

Output

For each test case, output a single integer in one line representing the number of different minimum spanning trees in the graph.
The answer may be quite large. You just need to calculate the remainder of the answer when divided by p (1<=p<=1000000000). p is above mentioned, appears in the first line of each test case.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5 10 12
2 5 3
2 4 2
3 1 3
3 4 2
1 2 3
5 4 3
5 1 3
4 1 1
5 3 3
3 2 3
0 0 0

Sample Output

1
4

Source

2012 ACM/ICPC Asia Regional Jinhua Online

Solution

联想Kruskal的过程,不同长度的边权之间对于图的联通性是没有影响的,因为如果不达到最大联通性就不会是最小生成树,那么对于每个权值相当的边单独考虑。

我们把小于当前枚举边的边缩成一个联通块,那么对于现在加进来的边可能会形成一些新的联通块。

我们再对于每个联通块分别考虑形成这个联通块的方案,最后相乘就是此时这类边的方案。形成这个联通块的方案就是这个联通块的生成树个数,用矩阵树定理算一下就好了。

复杂度$O(n^3)$,这个复杂度是基于相同权值的边的最大个数的立方的。

细节:取模注意正负数。

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
#include <bits/stdc++.h>
using namespace std;
#define IL inline
#define rep(i, j, k) for (int i = j; i <= k; ++i)
IL int read() {
char ch = getchar(); int u = 0, f = 1;
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
return u * f;
}
const int maxn = 105, maxm = 1005;
int fa[maxn], ka[maxn]; bool vis[maxn];
int findf(int x, int *f) { return f[x] == x ? x : f[x] = findf(f[x], f); }
int n, m, p;
IL int pls(int x, int y) { x += y; return x >= p ? x - p : x; }
IL int dec(int x, int y) { x -= y; return x < 0 ? x + p : x; }
IL int mul(int x, int y) { return 1ll * x * y % p; }
class ed{public: int u, v, w; }e[maxm];
IL bool cmp(ed x, ed y) { return x.w < y.w; }
vector<int>blk[maxn];
int mat[maxn][maxn], g[maxn][maxn], ans = 1;
int det(int c[][maxn], int n) {
int rtn = 1;
rep(i, 0, n-1) rep(j, 0, n-1) c[i][j] = (c[i][j] % p + p) % p;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
while (c[j][i]) {
int t = c[i][i] / c[j][i];
for (int k = i; k < n; ++k) c[i][k] = dec(c[i][k], mul(c[j][k], t));
swap(c[i], c[j]);
rtn = -rtn; rtn = (rtn % p + p) % p;
}
}
if (c[i][i] == 0) return 0;
rtn = mul(rtn, c[i][i]);
}
return rtn;
}
IL void calc_matrix_tree() {
rep(i, 1, n) if (vis[i]) blk[findf(i, ka)].push_back(i), vis[i] = 0;
rep(i, 1, n) if (blk[i].size() > 1) {
memset(mat, 0, sizeof mat);
for (int j = 0; j < blk[i].size(); ++j) {
for (int k = j + 1; k < blk[i].size(); ++k) {
int u = blk[i][j]; int v = blk[i][k];
if (g[u][v]) {
mat[k][j] = (mat[j][k] -= g[u][v]);
mat[k][k] += g[u][v];
mat[j][j] += g[u][v];
}
}
}
int temp = det(mat, blk[i].size() - 1);
ans = mul(ans, temp);
for (int j = 0; j < blk[i].size(); ++j) fa[blk[i][j]] = i;
}
rep(i, 1, n) blk[i].clear(), ka[i] = fa[i] = findf(i, fa);
memset(g, 0, sizeof g);
}
int main() {
while (true) {
n = read(), m = read(), p = read(); ans = 1;
memset(g, 0, sizeof g);
if (!n) break;
rep(i, 1, n) fa[i] = ka[i] = i;
rep(i, 1, m) e[i].u = read(), e[i].v = read(), e[i].w = read();
sort(e + 1, e + 1 + m, cmp);
rep(i, 1, m + 1) {
if (i != 1 && e[i].w != e[i - 1].w || i == m + 1) calc_matrix_tree();
if (i == m + 1) break;
int u = findf(e[i].u, fa); int v = findf(e[i].v, fa);
if (u != v) {
vis[v] = vis[u] = 1;
ka[findf(v, ka)] = findf(u, ka);
g[u][v]++; g[v][u]++;
}
}
int flag = 1;
rep(i, 2, n) if (fa[i] != fa[i - 1]) flag = 0;
printf("%d\n", flag ? ans % p : 0);
}
return 0;
}