CSC3100 Data Structures Assignment 3: Graph Spanning Tree
CSC3100 Assignment 3
Marking Criterion:
- The full score of theassignment is 100 marks.
- We have two problems in this assignment with 20 test cases each.
- Zero mark is given if: there is no submission; a normal submission fails both test A and test B. Running Environment:
- The submissions will be evaluated in the course’s OJ system running Java SE version 17 .
- The submission is only allowed to import four packages of (java.lang.; java.util.; java.math.; java.io.) included in Java SDK. No other packages are allowed.
- All students will have an opportunity to test their programs in the OJ platform prior to the
Submission Guidelines:
- Inconsistency with or violation from the guideline leads to marks deduction.
- It is the students’ responsibility to read this assignment document and submission guidelines carefully and in detail. No argument will be accepted on issues that have been specified clearly in these d ocuments. number of methods Input file: standard input Output file: standard output Time limit: 5 seconds Memory limit: 512 megabytes You are given an weighted undirected connected graph G(V; E), wherejVj=n,jEj=m. Each edge e2Eis a triplet (u; v; w ), where u; v2Vare the connected vertices and wis the weight of the edge. From the definition of minimum spanning tree, one undirected connected graph may have different minimum spanning trees.
You need to answer the number of methods to select edges differently to generate minimal spanning tree of this graph G. Two methods are considered as different if and only if there exists an edge that one method selects it while the other does not.
Input
The first line contains two integers nandm, where n105; m5105, indicating the number of vertices and edges respectively. Next mlines, each line contains three integers u; v; w, indicating an edge. (1u; v; wn) Remark: For arbitrary integer x2[1; n], the number of edges (u; v; w )with w=xwon’t exceed 8.
Output
One line containing one integer, the number of methods to select edges differently to generate minimal spanning tree. Since the number may be very large, you only need to output the number mod 1000000007.
Example
standard input standard output 5 20 1 2 1 5 2 1 2 1 1 5 2 1 2 1 1 5 2 1 5 4 2 2 4 3 2 1 3 4 1 3 2 4 3 1 5 4 4 3 5 1 2 5 1 2 5 5 1 5 1 2 1 2 3 2 1 4 3 3 5 412 Page 1 of 2 Note There are 20 testcases, 50 marks in total. Here is the detailed testcase information. Testcase 1 - 6: n5; m20, 3 marks each. Testcase 7 - 10: n16; m100, 3 marks each. Testcase 11 - 12: n100000 ; m500000, for arbitrary integer x2[1; n], the number of edges (u; v; w )withw=xwon’t exceed 1, 3 marks each. Testcase 13 - 14: n100000 ; m500000, for arbitrary integer x2[1; n], the number of edges (u; v; w )withw=xwon’t exceed 2, 3 marks each. Testcase 15 - 16: n100000 ; m500000, for arbitrary integer x2[1; n], the number of edges (u; v; w )withw=xwon’t exceed 3, 2 marks each. Testcase 17 - 20: n100000 ; m500000, for arbitrary integer x2[1; n], the number of edges (u; v; w )withw=xwon’t exceed 8, 1 mark each. Page 2 of 2 minimal value Input file: standard input Output file: standard output Time limit: 10 seconds Memory limit: 512 megabytes
You are given an weighted undirected connected graph G(V; E ), wherejVj=n,jEj=m. Each edge e2Eis a triplet (u; v; w ), where u; v2Vare the connected vertices and wis the weight of the edge. In this problem, we add some extra limitations. Then you need to select the least cost edge set that makes the graph connected under the limitations.
Every limitation is a pair (x; y), indicating that your method needs to contain at least one edge between xth edge and yth edge. Input The first line contains two integers nandm, where n105; m5105, indicating the number of vertices and edges respectively. Next mlines, each line contains three integers u; v; w, indicating an edge. (1u; v; wn). Specifically, theith line indicates the i 1th edge. Then the next line contains one integer k(0k10), indicating there are klimitations. Next klines, each line contains two integers x; y(x; ym), indicating your method must select at least one edge between xth edge and yth edge. Output One line one integer, the minimal cost under the limitations. Example standard input standard output 5 20 2 3 1 3 5 1 5 2 1 5 1 2 1 5 2 5 2 2 2 1 2 1 4 3 1 4 3 2 1 5 4 1 5 1 3 5 3 4 5 4 5 5 1 4 5 3 1 5 1 2 1 2 3 2 2 4 3 3 5 4 1 20 138
Note There are 20 testcases, 50 marks in total. Testcase 1 - 10: n20; m100; k1, 3 marks each testcase. Testcase 11 - 12: n100000 ; m=n 1; k10, 3 marks each testcase. Testcase 13 - 14: n100000 ; m150000 ; k5, 3 marks each testcase. Testcase 15 - 16: n100000 ; m200000 ; k5, 2 marks each testcase. Testcase 17 - 20: n100000 ; m500000 ; k10, 1 mark each testcase.
