MSTS - Count Minimum Spanning Trees
Your task is simple in this problem: count the number of minimum spanning tree (Wikipedia) in a simple undirected graph. The number of minimum spanning trees mean in how many ways you can select a subset of the edges of the graphs which forms a minimum spanning tree.
Input
The first line of input contains two integers N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 1000). Nodes are labeled from 1 to N. In the following M lines, every line contains three integers ai, bi, ci, representing an undirected edge from node ai to node bi, with weight ci. (1 ≤ ai ≠ bi ≤ N, 1 ≤ ci ≤ 1,000,000,000). You can assume there is at most one edge between two nodes, and the graph described by input is connected.
Output
Print the answer % 31011.
Example
Input: 4 6 1 2 1 1 3 1 1 4 1 2 3 2 2 4 1 3 4 1 Output: 8
hide comments
Piyush Raman Srivastava:
2014-01-26 19:34:46
This question teaches a lot about MST, cayley's formula, kirchoff's matrix thm, laplace matrices, ... just sums up entire graph theory concepts on trees!! Phew!! ;) |
|
Walrus:
2012-02-23 12:32:50
wasted a lot of time before noticing that 31011 is not a prime, may this be helpful to others. |
Added by: | Bin Jin |
Date: | 2008-04-29 |
Time limit: | 1.333s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 CPP |
Resource: | Jiangsu TSC for Chinese NOI 08, day 2 |