CSC3100 Assignment 3
Important Notes:
the last submission will be used in evaluation of assignment marks.
7.
Question1.java” and “StudentID_A3_Question2.java”, respectively on the blackboard.
For example, a student “120000001” should submit two programs named as “120000001_
A3_Question1.java” and “120000001_A3_Question2.java”.
You don't need to consider the consistency of class name and file name since we won't run
the code you submitted on the blackboard. File misnaming or no submission on the blackboard
will lead to 5 demerit points.
4. OJ website: http://oj.cuhk.edu.cn/. If failed, please try http://10.26.200.13/.
submission is accepted!
3. Please also submit your final two programs and rename them as “StudentID_A3
1. The assignment is an individual project, to be finished with one’s own effort.
2. The Submission deadline is 8pm Jul. 16, 2023 (Sunday). The deadline is tight. No late
_
If you are off
campus, please use VPN to access the OJ.
5. Access code: csc3100assignment3
6. Each student is only permitted to submit code to OJ up to 50 times for each problem. Only
Plagiarism is strictly forbidden, regardless of the role in the process. Notably, ten consecutive
lines of identical codes are treated as plagiarism. Depending on the seriousness of the
plagiarism, 30%-100% of marks will be deducted.
Marking Criterion:
1. The full score of the assignment 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:
1. The submissions will be evaluated in the course’s OJ system running Java SE version 17.
2. 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.
3. All students will have an opportunity to test their programs in the OJ platform prior to the
official submission.
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 documents.
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), where |V | = n, |E| = m. Each edge
e ∈ E is a triplet (u, v, w), where u, v ∈ V are the connected vertices and w is 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 n and m, where n ≤ 105
, m ≤ 5 × 105
, indicating the number of
vertices and edges respectively.
Next m lines, each line contains three integers u, v, w, indicating an edge.(1 ≤ u, v, w ≤ n)
Remark: For arbitrary integer x ∈ [1, n], the number of edges (u, v, w) with w = x won’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 4
12
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 x ∈ [1, n], the number of edges
(u, v, w) with w = x won’t exceed 1, 3 marks each.
Testcase 13 - 14: n ≤ 100000, m ≤ 500000, for arbitrary integer x ∈ [1, n], the number of edges
(u, v, w) with w = x won’t exceed 2, 3 marks each.
Testcase 15 - 16: n ≤ 100000, m ≤ 500000, for arbitrary integer x ∈ [1, n], the number of edges
(u, v, w) with w = x won’t exceed 3, 2 marks each.
Testcase 17 - 20: n ≤ 100000, m ≤ 500000, for arbitrary integer x ∈ [1, n], the number of edges
(u, v, w) with w = x won’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), where |V | = n, |E| = m. Each edge
e ∈ E is a triplet (u, v, w), where u, v ∈ V are the connected vertices and w is 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
x th edge and y th edge.
Input
The first line contains two integers n and m, where n ≤ 105
, m ≤ 5 × 105
, indicating the number of
vertices and edges respectively.
Next m lines, each line contains three integers u, v, w, indicating an edge.(1 ≤ u, v, w ≤ n). Specifically,
the i th line indicates the i − 1 th edge.
Then the next line contains one integer k(0 ≤ k ≤ 10), indicating there are k limitations.
Next k lines, each line contains two integers x, y(x, y ≤ m), indicating your method must select at least
one edge between x th edge and y th 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 13
8
Page 1 of 2
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 = n − 1, 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.
Page 2 of 2