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