MCIPC Contest 2 P5 - Holiday Chocolates

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

This winter at Martingrove, you have decided to help out a fundraiser that is selling chocolates. In the fundraiser, N students, numbered from 1 to N, have ordered chocolates, where the i^\text{th} student has ordered C_i chocolates for themselves. Additionally, when a student orders chocolates for themselves, they can also choose to order chocolates for some friends. Because of this, the fundraiser got M additional orders of chocolates, where in every additional order i, student u_i buys student v_i some chocolates.

However, as a part of a grand marketing scheme, if student u_i wants to buy student v_i chocolates, student u_i must order student v_i the same amount of chocolates that student u_i received, including the ones that student u_i bought for themselves. Note that a student cannot give themselves another order of chocolates, or give another student multiple orders of chocolates.

Because you have been tasked with delivering the chocolates, and you do not like hard work, you wish for there to be as few sales of chocolate as possible. You can coerce K people to not buy themselves chocolates, i.e., you can set K of the C_i to 0. However, they will still buy chocolates for their friends. What is the minimum amount of chocolates you will have to deliver?

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq M \leq 2 \times 10^5

0 \leq K \leq N

1 \leq C_i \leq 10^6

1 \leq u_i, v_i \leq N, u_i \neq v_i

The pair (u_i, v_i) is unique.

Before setting K of the C_i to 0, the total number of chocolates needed to be delivered will be less than 10^{18}.

There does not exist a cycle of students a_1, a_2, \dots, a_L such that student a_1 sent chocolates to student a_2, student a_2 sent chocolates to student a_3, \dots, student a_L sent chocolates to student a_1.

Subtask 1 [20%]

M = N - 1

Each student can send chocolates to at most 1 other student and can also receive chocolates from at most 1 other student.

Subtask 2 [30%]

K = 0

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains the integers N, M, and K, separated by a space.

The second line contains N space separated integers, where the i^\text{th} integer represents the number of chocolates C_i the i^\text{th} person will buy for themselves.

The i^\text{th} line of the next M lines will contain the integers u_i and v_i separated by a space, where student u_i will give chocolates to student v_i.

Output Specification

Output a single integer, the minimum number of chocolates which you will have to deliver after coercing K students into not buying chocolates for themselves.

Sample Input 1

4 4 1
1 5 1 1
1 2
2 3
3 4
2 4

Sample Output 1

8

Explanation for Sample 1

Student 1 buys themselves 1 chocolate, receiving 1 chocolate in total.

Student 2 buys themselves 5 chocolates and receives 1 chocolate from student 1, receiving 6 chocolates in total.

Student 3 buys themselves 1 chocolate, and receives 6 chocolates from student 2, receiving 7 chocolates in total.

Student 4 buys themselves 1 chocolate, receives 6 chocolates from student 2 and also receives 7 chocolates from student 3, receiving 14 chocolates in total.

Before preventing K of the students from buying themselves chocolates, the total amount of chocolates needed to be delivered is 1 + 6 + 7 + 14 = 28.

The optimal solution is to make student 2 not buy themselves chocolates, which results in 8 chocolates needing to be delivered.

Sample Input 2

6 8 3
3 4 2 5 10 1
1 3
1 2
1 4
2 4
4 5
3 5
5 6
2 5

Sample Output 2

22

Comments

There are no comments at the moment.