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

Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 7429  Solved: 3098

[][][]

Description

　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。

Input

　　第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,0

00。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。

Output

　　输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。

Sample Input

4 6

1 2 1

1 3 1

1 4 1

2 3 2

2 4 1

3 4 1

Sample Output

8

 

题目链接：

　　　　 

Solution

　　首先可以发现在不同的最小生成树中，同权值的边的数量是一样的。。

　　于是可以将每种权值的边的贡献分开算，然后用乘法原理就可以了。。

　　对于某一种颜色，直接爆搜。。。感觉复杂度好像不太对。。。但是过了。。。

　　算了反正都不知道多久之前写的了。。。

代码

#include
      
       #include
       
        #include
        
         #define M 1010#define mod 31011using namespace std;int n,m,cnt,tot;int f[M],w[M],sum[M];bool c[M];struct edge{    int l,r,w;}e[M],a[M];bool cmp(edge p,edge q){return p.w
        
       
      

　　

　　

This passage is made by Iscream-2001.