Description

https://cool.ntu.edu.tw/courses/3275/assignments/22192 (Prof. Yao-Wen Chang’s class) https://cool.ntu.edu.tw/courses/3304/assignments/22193 (Prof. James Chien-Mo Li’s class)
Problem: Cycle Breaking

(a) weighted undirected graph (b) weighted directed graph
Figure 1: Graphs with cycles.
Input
Output
The output file should report the total weight of removed edges to make the input graph acyclic, followed by a list of these removed edges and their weights. The output edges can be in arbitrary order. If the input graph has no cycles, you should output a line with single “0” (zero) in your output file.
Here are some input/output examples:
Sample Input 1 Sample Output 1 Sample Input 2 Sample Output 2
u 8 d 5
8 0 1 3 8 4 3 5
9 3 4 5 9
0 1 3 0 1 3
0 2 5 0 2 5
1 3 10 1 4 8
1 4 8 2 5 9
2 5 9 3 1 10
3 4 5 3 5 11
3 5 11 4 3 5
3 6 12 4 7 6
4 7 6 6 3 12
0 0
Command-line Parameter:
The executable binary must be named as ‘cb” and use the following command format.
./cb <input file name> <output file name>
For example, if you would like to run your binary for the input file 1.in and generate a solution named 1.out, the command is as follows:
./cb 1.in 1.out
Compilation:
We expect that your code can be compiled and run as follows. Type the following commands under <student id> pa3/ directory,
make
./bin/cb inputs/<input file name> outputs/<output file name>
Required Files:
You need to create a directory named <student id> pa3/ (e.g. b07901000 pa3/) (the student ID should start with a lowercase letter) which must contain the following documents:
A directory named src/ containing your source codes (e.g. cyclebreaker.cpp): only *.h, *.hpp, *.c,
*.cpp are allowed in src/, and no directories are allowed in src/;
A directory named bin/ containing your executable binary named cb;
A directory named doc/ containing your report;
A makefile named makefile that produces an executable binary from your source codes by simply typing
“make”: the binary should be generated under the directory <student id> pa3/bin/;
A text readme file named README describing how to compile and run your program.
A report named report.pdf on the data structures used in your program and your findings in this programming assignment.
We will use our own test cases, so you do NOT need to submit the input files. Nevertheless, you should have at least the following items in your *.tgz file.
src/<all your source code>
bin/cb doc/report.pdf makefile README
Submission Requirements:
1. Your program must be compilable and executable on EDA union servers.
2. The runtime limit for each test case is 1 minute.
3. Please use the following command to compress your directory into a .tgz file:
tar zcvf <filename>.tgz <your directory>
The submission file should be named as <student id> pa3.tgz (e.g. b07901000 pa3.tgz). For example, if your student ID is b07901000, then you should use the command below.
tar zcvf b07901000 pa3.tgz b07901000 pa3/
5. You are required to run the checkSubmitPA3.sh script to check if your .tgz submission file is correct. Suppose you are in the same level as the PA3 directory,
bash checkSubmitPA3.sh <your submission>
For example,
bash checkSubmitPA3.sh b07901000 pa3.tgz
Language/Platform:
1. Language: C or C++.
2. Platform: Linux.
Evaluation:
For undirected graph instances, an individual score per test case is determined by the correctness of the output result as well as the file format. For directed graph instances, the score is determined by not only correctness but also your rank of quality (total weight) compared with all submitted PAs. For fair evaluation, please apply the -O3 optimization for the compilation. Six input test cases are provided and more hidden test cases will be used for the final test.
References:
Breadth-first search, depth-first search, minimum spanning trees.
For any questions, please email Yi-Ting Lin at f07943102@ntu.edu.tw. Thank you so much for your cooperation. Have fun with this programming assignment!