P4208-[JSOI2008]最小生成树计数
题目:
题目描述:
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。
输入格式:
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。
接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。
数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
输出格式:
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
样例:
样例输入1:
1
2
3
4
5
6
7
| 4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
|
样例输出1:
思路:
实现:
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
| #include "ybwhead/ios.h"
const int maxn = 1e3 + 10;
const int mod = 31011;
struct Edge
{
int now, to, val;
} edge[maxn];
struct Mintree
{
int l, r, val;
} mintree[maxn];
int fa[maxn];
int n, m, sum;
int cmp(Edge a, Edge b)
{
return a.val < b.val;
}
int findfa(int x)
{
if (x == fa[x])
return x;
return x = findfa(fa[x]);
}
void dfs(int x, int now, int k)
{
if (now == mintree[x].r + 1)
{
if (k == mintree[x].val)
sum++;
return;
}
int fax = findfa(edge[now].now), fay = findfa(edge[now].to);
if (fax != fay)
{
fa[fax] = fay;
dfs(x, now + 1, k + 1);
fa[fax] = fax;
fa[fay] = fay;
}
dfs(x, now + 1, k);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
fa[i] = i;
}
for (int i = 1; i <= m; i++)
{
cin >> edge[i].now >> edge[i].to >> edge[i].val;
}
sort(edge + 1, edge + m + 1, cmp);
int cnt = 0, cntt = 0;
for (int i = 1; i <= m; i++)
{
if (edge[i].val != edge[i - 1].val)
{
cnt++;
mintree[cnt].l = i;
mintree[cnt - 1].r = i - 1;
}
int fax = findfa(edge[i].now);
int fay = findfa(edge[i].to);
if (fax != fay)
{
fa[fax] = fay;
mintree[cnt].val++;
cntt++;
}
}
mintree[cnt].r = m;
if (cntt != n - 1)
{
yout << 0 << endl;
return 0;
}
int ans = 1;
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= cnt; i++)
{
sum = 0;
dfs(i, mintree[i].l, 0);
ans = (ans * sum) % mod;
for (int j = mintree[i].l; j <= mintree[i].r; j++)
{
int fax = findfa(edge[j].now), fay = findfa(edge[j].to);
if (fax != fay)
fa[fax] = fay;
}
}
yout << ans << endl;
return 0;
}
|