codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1711B.md (2810B)


      1 Source: https://codeforces.com/problemset/problem/1711/B
      2 
      3 B. Party
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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, \dots, n$. If member $i$ is not invited, the party will gain an unhappiness value of $a_i$.
     22 
     23 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.
     24 
     25 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.
     26 
     27 What is the minimum possible total unhappiness value of the party, respecting the constraint that the total number of cakes eaten is even?
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows.
     32 
     33 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \leq 10^5$, $0 \leq m \leq \min(10^5,\frac{n(n-1)}{2})$) — the number of club members and pairs of friends.
     34 
     35 The second line of each test case contains $n$ integers $a_1,a_2, \dots,a_n$ ($0 \leq a_i \leq 10^4$) — the unhappiness value array.
     36 
     37 Each of the next $m$ lines contains two integers $x$ and $y$ ($1 \leq x,y \leq n$, $x \neq y$) indicating that $x$ and $y$ are friends. Each unordered pair $(x,y)$ appears at most once in each test case.
     38 
     39 It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $10^5$.
     40 
     41 Output
     42 
     43 For each test case, print a line containing a single integer – the minimum possible unhappiness value of a valid party.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 1 0
     53 
     54 1
     55 
     56 3 1
     57 
     58 2 1 3
     59 
     60 1 3
     61 
     62 5 5
     63 
     64 1 2 3 4 5
     65 
     66 1 2
     67 
     68 1 3
     69 
     70 1 4
     71 
     72 1 5
     73 
     74 2 3
     75 
     76 5 5
     77 
     78 1 1 1 1 1
     79 
     80 1 2
     81 
     82 2 3
     83 
     84 3 4
     85 
     86 4 5
     87 
     88 5 1
     89 ```
     90 
     91 Output
     92 
     93 ```
     94 0
     95 2
     96 3
     97 2
     98 ```
     99 
    100 Note
    101 
    102 In the first test case, all members can be invited. So the unhappiness value is $0$.
    103 
    104 In the second test case, the following options are possible:
    105 
    106 * invite $1$ and $2$ ($0$ cakes eaten, unhappiness value equal to $3$);
    107 * invite $2$ and $3$ ($0$ cakes eaten, unhappiness value equal to $2$);
    108 * invite only $1$ ($0$ cakes eaten, unhappiness value equal to $4$);
    109 * invite only $2$ ($0$ cakes eaten, unhappiness value equal to $5$);
    110 * invite only $3$ ($0$ cakes eaten, unhappiness value equal to $3$);
    111 * invite nobody ($0$ cakes eaten, unhappiness value equal to $6$).
    112 
    113 The minimum unhappiness value is achieved by inviting $2$ and $3$.
    114 
    115 In the third test case, inviting members $3,4,5$ generates a valid party with the minimum possible unhappiness value.