Problem Description
Although Rar the Cat has been selling sardines, he still does not have enough money to pay for his extravagant spendings on ikan bilis. Due to this, he was on the look out for part time jobs.
While walking around, he chanced upon a part time job offer - "Angler fish supervisor, 10pm to 5am daily"
Due to recent green efforts, angler fishes are used to illuminate roads in Catland. This not only allows Catland to cut down on electricity bills, but also makes the road more attractive (for cats).
In Catland, the road network can be expressed as a graph consisting N intersections (nodes) and E bi-directional roads (edges). Angler fishes must be stationed at nodes road intersections in order to enhance the safety of the intersections. However, not all road intersection require an angler fish but each road must start OR end at a node intersection with an angler fish.
The mayor of Catland has a fixed budget for keeping the roads lit during the night and Rar the Cat's salary is part of this budget. Furthermore, each angler fish has to be hired and the cost of hiring a particular angler fish varies with the road intersection it is assigned to. The cost of hirind angler fish contributes to the same budget too.
Rar the Cat has thus devised a shrewd money making plan. He plans to select the most optimal combination of angler fishes to hire, so that the cost to hire the angler fishes is the minimum. That way, he will earn the maximum amount of money as the budget is fixed.
Being an awesome programmer, Rar the Cat knows that this question is NP-Hard, meaning that a polynomial solution does not exist for a general graph. Hence, he is not sure whether his plan is the most optimal or not and challenges you to match or better his plan! He has promised to share the earnings with you via points in this selection test!
Rar the Cat has attached the input testcases as 'Attachments' for this problem. The input testcases follows the following input format.
Input
The first line of input consists of 2 integers, N and E. N is the number of road intersections (nodes) of the road network and E is the number of roads (edges). Road intersections are numbered from 0 to N-1 for convenience.
The second line of input consists of N integers, the first number denotes the amount required to hire an angler fish for the road intersection labelled 0. The second number denotes the amount required to hire an angler fish for the road intersection numbered 1. In general, the ith integer represents the cost to hire an angler fish for the road intersection labelled i-1
The cost to hire an angler fish will be non-negative and will not exceed 231-1 (will fit into a signed 32-bit integer). However, the optimal cost of hiring all the angler fishes might not fit into a 32-bit signed integer, please use a 64-bit signed integer (long long) instead.
The following E lines of input will consist of 2 integers each A and B. This indicates that there is a road that exists between road intersection numbered A and the road intersection numbered B. A and B will be unique (will not appear in the input twice in the same/different order) and A will not be equal to B.
Output
You are to output at most N integers as output, one on each line.
These integers represent the road intersections you intend to hire angler fishes for.
For the output to be valid, the integers must lie within the range 0 to N-1 and must not repeat. The order of output does not matter as long as the total cost is optimal.
You do not need to output the number of angler fishes you intend to hire.
Subtasks
Subtask 1 (10%): N ≤ 30
Subtask 2 (20%): N ≤ 100,000 and the graph is guaranteed to be a line.
Subtask 3 (30%): N ≤ 100,000 and the graph is guaranteed to be a tree.
Subtask 4 (40%): N ≤ 100,000
Do note that E is bounded by N and you can find the exact value by peering into the testcases provided.
Scoring
This is an output only question. You are just supposed to submit the output to the judge. You will receive partial marks according to the following formula:
Let the cost of your plan be C and the cost of Rar the Cat's plan be R.
If your plan does not result in all roads being monitored by an angler fish, you will receive 0 points for that testcase.
If C &eq; R, you will receive 100% of the score for that testcase.
If C < R, you will receive 105% of the score for that testcase.
If R*2 ≤ C < R, you will receive partial credit based on the following formula: 90*(2 - C/R)3%
If C > R*2, you will receive 0% of the score for that testcase.
Additional Notes
Although this is an output only problem, we recommend you attach/copy the source codes of the programs you have written for this program under 'save.txt'. This is to ensure that your code will be safe with the judging server in the event that your computer crashes or a relocation needs to be done.
'save.txt' will not be graded and you can copy the source codes of more than one program inside the area provided.
Each testcase is worth 10 points and '1.in.txt' belongs to subtask 1, '2.in.txt' and '3.in.txt' belongs to subtask 2, '4.in.txt', '5.in.txt' and '6.in.txt' belongs to subtask 3 and '7.in.txt', '8.in.txt', '9.in.txt', '10.in.txt' belongs to subtask 4.
You will receive the minimum score of all the testcases in subtask 1, 2 and 3. For subtask 4, you will receive the average score of all the testcases in subtask 4.
Please submit the corresponding 'x.out.txt' file for the xth testcase.
Sample Testcase 1
7 8
1 1 1 2 1 1 1
0 1
1 3
0 2
2 3
3 4
4 6
3 5
5 6
Sample Output 1
1
2
4
5
By choosing to hire anglerfishes to be stationed at the above road intersections (1, 2, 4 & 5), the total cost of hiring them is 4. This ensures that each road touches at least one intersection with an angler fish.
An alternative choice would be to hire anglerfishes at intersections (0, 3 & 6) and that will obtain full credit as well.
Sample Testcase 2
7 8
1 1 1 1 1 1 1
0 1
1 3
0 2
2 3
3 4
4 6
3 5
5 6
Sample Output 2
6
0
3
The total cost of hiring anglerfishes to make sure each road touches at least an intersection with an anglerfish is 3. This is the only most optimal way. Do note that the order of output does not matter.