I have seen a problem about bipartite matching on a special weighted graph and i would like to know the solution. The graph is similar to 875F - Royal Questions where nodes in one sides have at most 2 neighbours and the weight of these two edges are the same. However, each edge has 2 weights Ai and Bi, and the total weight is (sum of A)*(sum of B). The task is to find a maximum matching with highest total weight. N<=10000 and A,B<=30 where N is the number of nodes. Could someone give hints/solutions about this problem? Million thanks!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2024 10:16:39 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by gamegame (previous revision, new revision, compare).
Let's find optimal sum with weights of right part = 0, and optimal sum with weights of left part = 0.
Answer is sumA * sumB
Could you elaborate more about that = 0? Do you mean that you set every Bi to 0 then find max sumA? Thanks
Yes
How about this. Your method: (3+2)*(3+2) = 25 while max weight = (3+2)*(3+1) = 20Graph
Oh, sorry, i thought that each vertex has a weight, not an edge.
This problem is basically Time is Money with matching instead of spanning tree I think
I think this comment is incorrect, can someone clear this up?
That trick works for Time is Money because in that problem we want to minimize and the shape being convex means that the first point that lies outside of that shape is in the border of the convex hull, but here we want to maximize so the same doesn't apply.