Блог пользователя vamaddur

Автор vamaddur, история, 7 лет назад, По-английски

Given a graph with at most 2*10^5 nodes and 2*10^5 edges, bicolor the graph such that the difference between the number of nodes with each color is minimized, and print out that difference.

I am able to bicolor each of the connected components, and find the number of each color in each component. I tried to make the final step of finding the minimum difference into the subset sum problem before realizing that there are restrictions on what numbers can go together.

E.g. I have components (Red, Blue) as (1, 5) and (2, 4); the optimal subset sum solution would normally be to put the 1 and 5 together, and the 2 and 4 together. However, the (1, 5) pair and (2, 4) pair are component pairs, which is not allowed.

Please help, and thanks in advance!

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

You can use a knapsack algorithm in SsqrtS with S being the sum of values. You can find out more about it in the editorial and discussions of this problem. Let N be the total number of nodes. Let's say we have a pair (A, B) with A<=B. We add A to the value Left and B — A to an array v. Now, all you need to do is to choose some items from the array v so that their sum plus Left will be as close as possible to N / 2, which you can do with that modified version of knapsack. I denoted that sum by Left because it'll account for the number of nodes on the left side.