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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена \in на ∈)
(Массовая правка: замена \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 \cap S_i|=1</m>.
+
* Найти систему представителей <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 (рид-онли просмотр)