Hardprob/Maximum Capacity Representatives — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена \cap на ∩) |
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)_(\w),\s*…\s*,\s*(\w)_(\w)<\/m> на <em>\1<sub>\2</sub>, …, \3<sub>\4</sub></em>) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Непересекающиеся множества < | + | * Непересекающиеся множества <em>S<sub>1</sub>, …, S<sub>m</sub></em>, и для любых <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 ∩ S_i|=1</m>. | * Найти систему представителей <em>T</em>, т.е. набор <em>T</em>, такой, что для любого <em>i</em>, <m>|T ∩ S_i|=1</m>. | ||
Текущая версия на 22:54, 17 апреля 2023
- Непересекающиеся множества S1, …, Sm, и для любых , чтобы была задана неотрицательная емкость c(x,y).
- Найти систему представителей T, т.е. набор T, такой, что для любого i, .
- Максимизировать «емкость» системы представителей, т.е.
.
Задача в лаб22 (рид-онли просмотр)