Given N points in one set(S1) and M points in another set(S2), Choose some edges between points from Set S1 to set S2 such that sum of edges(distances) is minimum and every vertex is chosen atleast once.
Can someone help me solving this problem. Thanks!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
This is exactly minimum-cost maximal flow problem.
How to satisfy "every vertex is chosen at least once"?
Instead of infinite edge for vertex you use one infinite edge and one edge with capacity 1 and const -BIG. After that, you'll add BIG*vertices to the answer
If set 2 doesn't have more numbers than set 1 then, Setting capacity of edges of source to set 1 and set 1 to set 2 equals to 1 and Setting capacity of edges from set 2 to sink to infinity should work. right?