【bzoj1543】生成树计数

2015.04.25 14:42 Sat | 24次阅读 | 旧日oi | 固定链接 | 源码

Description

给定一个连通的带边权的图(允许自环和重边),求不同的最小生成树个数。两个生成树不同当它们所用的边的序号不同,换句话说,重边算多次。

Input

第一行n,m,表示点数和边数(1<=n<=50000,1<=m<=100000) 下接m行,每行3个数k1,k2,w,表示k1和k2之间有一条权值为w 的边。

Output

仅一行一个数:生成树个数 mod 1000003(质数)

Sample Input

3 5
1 2 6
1 2 6
2 3 6
3 1 6
3 3 8

Sample Output

5
注:不会存在5条及5条以上的边,他们的边权是相同的。
样例解释:
5棵生成树分别如下(边按输入顺序标号):
(1,3) (2,3) (1,4) (2,4) (3,4)
5号边是自环。

题解

和1016代码几乎一样,数据范围大了一点,然后取模数不一样了,我还少打个0wa了一次TAT