Description
1 Introduction
Rhaenyra Targaryen, the first-born child of King Viserys I Targaryen, was considered the rightful heir to the Iron Throne. She was going to rule all the Westeros but her half-brother, Aegon Targaryen, seized the throne by force. Rhaenyra is now determined to reclaim the Iron Throne from Aegon. However, she heard from her consultants that Aegon started to gather support from all corners of Westeros to maintain his power.
She knows that in order to defeat Aegon, she needs to prevent him from gathering enough support. So she trusts your algorithm skills and asks you to help her take her rightful place as queen. Aegon’s main purpose is to construct the biggest army with soldiers from all the regions in King’s Landing. He began by sending envoys to The Reach, Riverlands, Dorne, The Vale of Arryn, The Westerlands, and The Stormlands, offering alliances and promises of rewards in exchange for support (e.g. troops).
He is pleased to receive enthusiastic responses from these 6 regions and begins to mobilize his forces. The regions are willing to send all their troops to King’s Landing but because of limited transportation resources, there are a limited amount of troops that can reach the King’s Landing. But Aegon and his consultants know how to maximize the number of troops that can come to King’s Landing to support him. For Rhaenyra to defeat Aegon, she must first know the size of the troops he’s gathering in King’s Landing.
Also, she wants to block the route of all the troops, so needs to know where to send her armies to. Your duty is to give this crucial information to Rhaenyra using your CmpE250 knowledge. 1
2 Details
• There are exactly 6 regions willing to send all the troops they have. • Each troop travels to King’s Landing and each troop has the same number of soldiers. • There are many cities in the routes of the troops and only a limited number of troops can travel between two cities due to transportation limitations and harsh conditions. Luckily, we know the capacity of each road. • If there is a road from one city to another, let’s say from city 1 to city 2, it doesn’t mean that there is also a road from 2 to 1.
• A region is most vulnerable when preparing to send all the troops it has and a road is most vulnerable when the troops are traveling at the maximum capacity of that road. Rheanyra wants to send her armies to the vulnerable regions and roads. She also wants to block all the troops going to King’s Landing, so you must find the cut with full capacities that add up to the maximum number of troops. (Sounds like a familiar problem. doesn’t it? :)) • There are no roads from cities to regions or from King’s Landing to cities/regions.
3 Input & Output
3.1 Input • The first line represents the total number of cities except King’s Landing. • The second line contains 6 integers, each representing the number of troops a region is willing to send. • The next 6 lines will give the ID of a region, the number of troops they are trying to send, the IDs of the cities that are reachable from the given region, and the capacity of the road from that region to that city. • Each next line will give the ID of a city, the IDs of the cities that are reachable from the given city, and the capacity of the road between these two cities. 2
3.2 Output • An integer, the maximum number of troops that can reach the King’s Landing. • (BONUS) Regions and roads (as pairs of vertices line by line) that Rhaenyra must send her armies to.
3.3 Example Input Explanation 4 There are 4 cities in the route, except King’s Landing. 50 40 60 29 43 20 r0 is willing to send 50 troops, r1 40, r2 60, r3 29, r4 43 and r5 20. r0 c0 25 The capacity of the road from r0 to city c0 is 25. r1 c0 20 c1 30 r2 There is no road from r2 to cities. r3 c2 9 r4 c3 7 r5 c3 18 KL 37 c0 c2 30 KL 19 The capacity of the road from c0 to c2 is 30, from c0 to the King’s Landing is 19. c1 c0 10 c2 c0 19 KL 33 c3 KL 15 Table 1: Sample Input with Explanations 3 r0 25/50 r1 18/40 r2 0/60 r3 9/29 r4 7/43 r5 20/20 c0 c1 c2 c3 KL 25/25 18/20 0/30 9/9 7/7 0/18 20/37 24/30 0/10 19/19 0/19 33/33 7/15 Vulnerable roads and regions that must be blocked are shown in red. A/B indicates that A troops are using the road with B capacity. The dashed line shows the blocking cut.
Output Explanation 79 r5 r4 c3 c0 KL c2 KL Maximum number of troops. (20+7+33+19) These are vulnerable regions and roads, and the sum of their capacities are the maximum number of troops. Table 2: Expected Output File 4
4 Submission
Your code will be graded automatically. Therefore, it’s important that you follow the submission instructions. First, all of your source files should be collected under Project5/src. Then, you should zip the Project5 folder and rename it to .zip. This zip file will be submitted through moodle. Name of your main class must be project5.java. Your program will be compiled with the command below: javac -target 17 Project5/src/*.java -d ./ The input and output files can be in any folder. Design your code to accept the full path for file arguments.
Your program will be run with the command below: java project5 Make sure your final submission compiles and runs with these commands.
5 Grading The grading of this project is based on the automatic compilation and run and the success of your code in test cases. If your code compiles and runs with no error, then you will get 10/100 of the project grade. The rest of your grade will be the sum of collected points from each test case. If you provide the correct number of maximum troops for each test case, then you will receive 100 points. Finding the regions and roads is an optional task which is worth 15 bonus points. If your submission is not autorunnable, then you will receive 0 at first and then have to issue an objection.
6 Warnings 1. This is an individual project. 2. All source codes are checked automatically for similarity with other submissions and exercises from previous years. Do not copy codes from the internet or your friends. Make sure you write and submit your own code. Any sign of cheating will be penalized, and you will get -50 points for the project, and you will get F grade in case of recurrence in any other project. 5 3. There will be time limit on test cases, so the most important side of this project is to write your code in an efficient manner.
Even if your code is completely correct, you will not get full points if it is not efficient. 4. You can add as many files as you can as long as they are in the “src” folder and your project can be compiled as above. But the entry point of your program should be “project5.java”. 5. Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment or make your variable names unnecessarily long. This is very important for partial grading. 6
