Hardprob/Maximum Capacity Representatives — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена \cap на ∩)
(Массовая правка: замена 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}}}} -->
* Непересекающиеся множества <m>S_1, \ldots, S_m</m>, и для любых <m>i \neq j, x ∈  S_i, y
+
* Непересекающиеся множества <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 (рид-онли просмотр)