[Solution] Party solution codeforces – What is the minimum possible total unhappiness value of the party, respecting the constraint that the total number of cakes eaten is even?

Party solution codeforces – A club plans to hold a party and will invite some of its 𝑛n members. The 𝑛n members are identified by the numbers 1,2,,𝑛1,2,…,n. If member 𝑖i is not invited, the party will gain an unhappiness value of 𝑎𝑖ai.

Table of Contents

[Solution] Party solution codeforces

There are 𝑚m pairs of friends among the 𝑛n members. As per tradition, if both people from a friend pair are invited, they will share a cake at the party. The total number of cakes eaten will be equal to the number of pairs of friends such that both members have been invited.

However, the club’s oven can only cook two cakes at a time. So, the club demands that the total number of cakes eaten is an even number.

What is the minimum possible total unhappiness value of the party, respecting the constraint that the total number of cakes eaten is even?

[Solution] Party solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1041≤t≤104). The description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (1𝑛1051≤n≤1050𝑚min(105,𝑛(𝑛1)2)0≤m≤min(105,n(n−1)2)) — the number of club members and pairs of friends.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖1040≤ai≤104) — the unhappiness value array.

Each of the next 𝑚m lines contains two integers 𝑥x and 𝑦y (1𝑥,𝑦𝑛1≤x,y≤n𝑥𝑦x≠y) indicating that 𝑥x and 𝑦y are friends. Each unordered pair (𝑥,𝑦)(x,y) appears at most once in each test case.

It is guaranteed that both the sum of 𝑛n and the sum of 𝑚m over all test cases do not exceed 105105.

Output

For each test case, print a line containing a single integer – the minimum possible unhappiness value of a valid party.

[Solution] Party solution codeforces

input

Copy
4
1 0
1
3 1
2 1 3
1 3
5 5
1 2 3 4 5
1 2
1 3
1 4
1 5
2 3
5 5
1 1 1 1 1
1 2
2 3
3 4
4 5
5 1
output

Copy
0
2
3
2

[Solution] Party solution codeforces

In the first test case, all members can be invited. So the unhappiness value is 00.

In the second test case, the following options are possible:

  • invite 11 and 22 (00 cakes eaten, unhappiness value equal to 33);
  • invite 22 and 33 (00 cakes eaten, unhappiness value equal to 22);
  • invite only 11 (00 cakes eaten, unhappiness value equal to 44);
  • invite only 22 (00 cakes eaten, unhappiness value equal to 55);
  • invite only 33 (00 cakes eaten, unhappiness value equal to 33);
  • invite nobody (00 cakes eaten, unhappiness value equal to 66).

The minimum unhappiness value is achieved by inviting 22 and 33.In the third test case, inviting members 3,4,53,4,5 generates a valid party with the minimum possible unhappiness value.

 

For Solution

Click Here

Leave a Comment