UniqueMST
2020 TCO Semi 1 · 2020-11-12 · by jy_25
Problem Statement
This problem has a non-standard time limit: 7 seconds.
You have a complete undirected graph with N labeled vertices. You have to assign a positive integer weight less than or equal to K to each of its N*(N-1)/2 edges.
Count all those assignments of weights such that the graph has a unique minimum spanning tree. Return the count modulo a prime number M .
Notes
- A tree is a connected graph with no cycles.
- A spanning subgraph of G is a subgraph that contains all vertices of the original graph G.
- A spanning tree of G is a spanning subgraph of G that is a tree.
- A minimum spanning tree of G is a spanning tree such that the sum of its edge weights is the smallest among all spanning trees of G.
Constraints
- N will be between 2 and 50, inclusive.
- K will be between 1 and 10 9 , inclusive.
- M will be a prime number between max(N, K) + 1 and 10 9 , inclusive.
2 5 29 Returns: 5
With just two vertices and a single edge between them the MST is always unique.
3 3 11 Returns: 4
As there are three vertices, the MST is unique if and only if the edge with maximum weight is unique. This happens for the following assignments of weights: There are 3 assignments where the edge weights are 1, 1, 2 in some order. There are 3 assignments where the edge weights are 1, 1, 3 in some order. There are 6 assignments where the edge weights are 1, 2, 3 in some order. There are 3 assignments where the edge weights are 2, 2, 3 in some order. Thus, the total number of good assignments of weights is 3 + 3 + 6 + 3 = 15 and the returned answer is (15 mod 11) = 4.
42 919191919 999999937 Returns: 440488107
2 1 928456201 Returns: 1
2 909162575 951257777 Returns: 909162575
7 2 998244353 Returns: 16807
For N = 7 and K = 2 the MST is unique if and only if all edges with weight 1 form exactly a spanning tree.
Submissions are judged against all 194 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class UniqueMST with a public method int count(int N, int K, int M) · 194 test cases · 2 s / 256 MB per case