oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

chessislands Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

chessislands.html

Ray the penguin has decided to repaint his extensive network of N icy islands (conveniently numbered 1..N) with a chess theme! Thus, he wishes to paint every island either black or white. Also, everyone knows that on a chessboard, white squares aren't next to white squares and black squares aren't next to black squares. Thus, in a similar vein, if two islands are connected by a bridge, one of them must be black and the other must be white. Also, since icy islands are already white (or at least, whitish), Ray only needs to buy some black paint now. Help him find the minimum amount of black paint he needs!

You are given the area of each island (in Ray-square-metres or Rm2), as well as a list of which islands are connected by bridges. It is guaranteed that there is a valid way to paint the islands such that no two connected islands have the same colour. Thus, output the minimum amount of area in Rm2 which needs to be painted black.

Note: Not all islands might be connected!

Input

On the first line are integers N and E, where E is the number of bridges. (1 ≤ N ≤ 50,000, 1 ≤ E ≤ 300,000)

The next N lines each contain one integer X, with the ith line representing the area of the island numbered i. (1 ≤ X ≤ 40,000).

The next E lines each contain two integers A and B, meaning that islands A and B are connected by a bridge.

Output

Output consists of a single line containing S, the minimum area which needs to be painted black.

Grading

For 50% of the test cases, all areas will be 1.

Sample Input 1

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

Sample Output 1

4

Explanation for Sample Output 1

By painting islands 1 and 3, we fulfill the given conditions and use 4 Rm2 of black paint. We could also paint islands 2, 4 and 5 black, but this would not be minimal, as it uses 11 Rm2 of black paint instead.

Tags

Graph Theory, NOI 2010 Selection Test

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100201s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o chessislands -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.