Hardprob/Maximum Capacity Representatives — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
* Найти систему представителей <em>T</em>, т.е. набор <em>T</em>, такой, что для любого <em>i</em>, <m>|T \cap S_i|=1</m>. | * Найти систему представителей <em>T</em>, т.е. набор <em>T</em>, такой, что для любого <em>i</em>, <m>|T \cap S_i|=1</m>. | ||
* Максимизировать «емкость» системы представителей, т.е. | * Максимизировать «емкость» системы представителей, т.е. | ||
| − | <m>$\sum_{x,y ∈ T}c(x,y) → \ | + | <m>$\sum_{x,y ∈ T}c(x,y) → \max</m>. |
---- | ---- | ||
Версия 10:50, 11 апреля 2023
- Непересекающиеся множества , и для любых , чтобы была задана неотрицательная емкость c(x,y).
- Найти систему представителей T, т.е. набор T, такой, что для любого i, .
- Максимизировать «емкость» системы представителей, т.е.
.
Задача в лаб17 (рид-онли просмотр)