最小生成树计数

定理

首先引入几个定理

  • 对于两个不同的最小生成树$A,B$(这里的不同指严格意义下的边不同),当且仅当对于长度为$w$的边,$A,B$所拥有的个数相等
  • 只连接长度$\leq w$的边,$A,B$连通性相同

证明略

思路

根据这几个定理,可以得到一个简单的思路

  • 将边长$w_i$离散化,因为对于最小生成树来说只需考虑大小关系

  • 求出最小生成树$A$,记录长度$w_i$的边使用的次数$cnt[w_i]$

  • 考虑Kruscal算法的过程,我们每次加边来联通两个联通块,所以假设当前考虑到长度为$w$的边,我们直接用暴搜考虑加边的方案数

  • 乘法原理计数

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
/***************************************************************
File name: I.cpp
Author: ljfcnyali
Create time: 2019年05月24日 星期五 08时38分49秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )

const int maxn = 2010;
const int INF = 0x3f3f3f3f;
const int Mod = 31011;

struct node
{
int u, v, w;
} a[maxn];

int n, m, f[maxn], cnt[maxn], sum, ans, W;

inline int cha(int x)
{
return f[x] == x ? x : cha(f[x]);
}

inline int cmp(node x, node y)
{
return x.w < y.w;
}

inline void Kruscal()
{
ans = sum = 0;
REP(i, 1, m)
{
int fx = cha(a[i].u), fy = cha(a[i].v);
if ( fx != fy )
{
f[fx] = fy; cnt[a[i].w] ++; ++ sum;
// printf("%d %d %d\n", a[i].u, a[i].v, a[i].w);
}
if ( sum == n - 1 ) { ans = 1; return ; }
}
}

inline int dfs(int x, int w, int s)
{
if ( s == cnt[w] ) return 1;
if ( a[x].w != w ) return 0;
int fx = cha(a[x].u), fy = cha(a[x].v), sum = 0;
if ( fx != fy ) { f[fx] = fy; sum = dfs(x + 1, w, s + 1); f[fx] = fx; }
return sum + dfs(x + 1, w, s);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
while ( ~scanf("%d%d", &n, &m) )
{
mem(a); mem(cnt); W = 1; REP(i, 1, n) f[i] = i;
REP(i, 1, m) scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);
sort ( a + 1, a + m + 1, cmp ); a[m + 1].w = INF;
REP(i, 1, m)
{
if ( a[i].w != a[i + 1].w ) a[i].w = W ++;
else a[i].w = W;
}
Kruscal();
if ( ans == 0 ) { printf("0\n"); continue ; }
REP(i, 1, n) f[i] = i;
REP(i, 1, m)
{
if ( !cnt[a[i].w] || a[i - 1].w == a[i].w ) continue ;
sum = dfs(i, a[i].w, 0);
ans = (ans * sum) % Mod;
for ( int j = i; j; ++ j )
{
if ( a[j].w != a[i].w ) break ;
int fx = cha(a[j].u), fy = cha(a[j].v);
if ( fx != fy ) f[fx] = fy;
}
}
printf("%d\n", ans);
}
return 0;
}