1. Homepage
2. Programming
3. CSC3100 Data Structures Assignment 3: Graph Spanning Tree

# CSC3100 Data Structures Assignment 3: Graph Spanning Tree

Hong KongCUHKCSC3100Data StructuresJavaGraphSpanning Tree

# CSC3100 Assignment 3

## Marking Criterion:

1. The full score of theassignment is 100 marks.
2. We have two problems in this assignment with 20 test cases each.
3. Zero mark is given if: there is no submission; a normal submission fails both test A and test B. Running Environment:
4. The submissions will be evaluated in the course’s OJ system running Java SE version 17 .
5. 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.
6. All students will have an opportunity to test their programs in the OJ platform prior to the

## Submission Guidelines:

1. Inconsistency with or violation from the guideline leads to marks deduction.
2. 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 ﬁle: standard input Output ﬁle: 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 deﬁnition of minimum spanning tree, one undirected connected graph may have diﬀerent minimum spanning trees.

You need to answer the number of methods to select edges diﬀerently to generate minimal spanning tree of this graph G. Two methods are considered as diﬀerent if and only if there exists an edge that one method selects it while the other does not.

### Input

The ﬁrst line contains two integers nandm, where n105; m5105, indicating the number of vertices and edges respectively. Next mlines, each line contains three integers u; v; w, indicating an edge. (1u; v; wn) 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 diﬀerently 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: n5; m20, 3 marks each. Testcase 7 - 10: n16; m100, 3 marks each. Testcase 11 - 12: n100000 ; m500000, for arbitrary integer x2[1; n], the number of edges (u; v; w )withw=xwon’t exceed 1, 3 marks each. Testcase 13 - 14: n100000 ; m500000, for arbitrary integer x2[1; n], the number of edges (u; v; w )withw=xwon’t exceed 2, 3 marks each. Testcase 15 - 16: n100000 ; m500000, for arbitrary integer x2[1; n], the number of edges (u; v; w )withw=xwon’t exceed 3, 2 marks each. Testcase 17 - 20: n100000 ; m500000, 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 ﬁle: standard input Output ﬁle: 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 ﬁrst line contains two integers nandm, where n105; m5105, indicating the number of vertices and edges respectively. Next mlines, each line contains three integers u; v; w, indicating an edge. (1u; v; wn). Speciﬁcally, theith line indicates the i1th edge. Then the next line contains one integer k(0k10), indicating there are klimitations. Next klines, each line contains two integers x; y(x; ym), 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: n20; m100; k1, 3 marks each testcase. Testcase 11 - 12: n100000 ; m=n1; k10, 3 marks each testcase. Testcase 13 - 14: n100000 ; m150000 ; k5, 3 marks each testcase. Testcase 15 - 16: n100000 ; m200000 ; k5, 2 marks each testcase. Testcase 17 - 20: n100000 ; m500000 ; k10, 1 mark each testcase.

## Get in Touch with Our Experts

WeChat
WhatsApp
Hong Kong代写,CUHK代写,CSC3100代写,Data Structures代写,Java代写,Graph代写,Spanning Tree代写,Hong Kong代编,CUHK代编,CSC3100代编,Data Structures代编,Java代编,Graph代编,Spanning Tree代编,Hong Kong代考,CUHK代考,CSC3100代考,Data Structures代考,Java代考,Graph代考,Spanning Tree代考,Hong Konghelp,CUHKhelp,CSC3100help,Data Structureshelp,Javahelp,Graphhelp,Spanning Treehelp,Hong Kong作业代写,CUHK作业代写,CSC3100作业代写,Data Structures作业代写,Java作业代写,Graph作业代写,Spanning Tree作业代写,Hong Kong编程代写,CUHK编程代写,CSC3100编程代写,Data Structures编程代写,Java编程代写,Graph编程代写,Spanning Tree编程代写,Hong Kongprogramming help,CUHKprogramming help,CSC3100programming help,Data Structuresprogramming help,Javaprogramming help,Graphprogramming help,Spanning Treeprogramming help,Hong Kongassignment help,CUHKassignment help,CSC3100assignment help,Data Structuresassignment help,Javaassignment help,Graphassignment help,Spanning Treeassignment help,Hong Kongsolution,CUHKsolution,CSC3100solution,Data Structuressolution,Javasolution,Graphsolution,Spanning Treesolution,