Вопрос задан 02.11.2026 в 21:02. Предмет Информатика. Спрашивает Маслова Алина.

A. Пир на полярной станции
Ограничение времени 2 секунды
Ограничение памяти 256.0 Мб
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
После успешного окончания кулинарных курсов Кеша, который всегда мечтал работать в Арктике, устроился на работу на изолированную полярную станцию. Когда он прибыл на станцию вместе с запасом свежих продуктов, её персонал сильно обрадовался и решил устроить небольшой праздник.
На этот праздник Кеша решил приготовить N видов свежевыжатых соков. Для приготовления соков требуется K различных овощей и фруктов, причём в состав одного сока может входить от 1 до K компонентов. Объём чаши соковыжималки, которой будет пользоваться Кеша, а также количество исходных материалов достаточны для того, чтобы приготовить весь объём требуемого сока за один раз.
По технологии, чашу соковыжималки надо помыть после приготовления каждого сока. Но Кеше не нравится эта операция, так как она расходует слишком много тёплой воды и занимает много времени... Он заметил, что если в состав следующего сока входят все компоненты, требуемые для изготовления предыдущего, то чашу можно и не мыть. Так, после приготовления яблочного сока можно обойтись без мытья чаши перед приготовлением яблочно-ананасового сока.
Помогите Иннокентию и рассчитайте минимальное количество операций мытья чаши, которые потребуются для приготовления всех соков. Естественно, после выполнения работы чаша должна быть чистой!

Формат ввода
В первой строке записываются целые величины N и K (1 ⩽ N, K ⩽ 300). Далее следуют N строк, каждая из которых описывает рецепт изготовления одного сока. Первое число этой строки m (1 ⩽ m ⩽ K) — количество компонентов сока. Далее следуют m различных целых чисел, каждое из которых находится в интервале от 1 до K включительно — номера компонентов, которые входят в состав соответствующего сока. Гарантируется, что набор компонентов различен для различных соков.

Формат вывода
Выведите единственное число — минимальное количество операций по мытью чаши.
Примеры
Ввод Вывод: 2
3 2
1 1
1 2
2 1 2
Ввод Вывод 4
4 4
1 1
1 2
1 3
1 4
Решать на любом языке программирования.

Перейти к ответам

Отвечу на вопрос мгновенно! Нейросеть ChatGPT. Жми!

Ответы на вопрос

Отвечает Мойсак Ксения.

Соки можно готовить подряд без мытья, если набор компонентов следующего сока содержит все компоненты предыдущего. Поэтому рецепты нужно разбить на минимальное число цепочек: в каждой цепочке каждый следующий набор содержит предыдущий.

Каждая цепочка требует одного мытья — после её завершения, так как по условию чаша должна остаться чистой. Минимальное число цепочек в таком графе равно \(N-M\), где \(M\) — размер максимального паросочетания.

Построим двудольный граф: слева и справа находятся все рецепты. Проводим ребро \(i \to j\), если компоненты рецепта \(i\) являются подмножеством компонентов рецепта \(j\). Затем находим максимальное паросочетание алгоритмом Куна.

Сложность: \(O(N^3K)\) в худшем случае, при \(N,K\leq300\) этого достаточно.

Код C++17:

#include <bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, k;
cin >> n >> k;
vector<vector<int>> a(n, vector<int>(k + 1));
for (int i = 0; i < n; ++i) {
int m; cin >> m;
while (m--) {
int x; cin >> x;
a[i][x] = 1;
}
}

vector<vector<int>> g(n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) if (i != j) {
bool ok = true;
for (int x = 1; x <= k; ++x)
if (a[i][x] && !a[j][x]) ok = false;
if (ok) g[i].push_back(j);
}

vector<int> mt(n, -1), used;
function<bool(int)> dfs = [&](int v) {
if (used[v]) return false;
used[v] = 1;
for (int to : g[v])
if (mt[to] == -1 || dfs(mt[to])) {
mt[to] = v;
return true;
}
return false;
};

int matching = 0;
for (int v = 0; v < n; ++v) {
used.assign(n, 0);
if (dfs(v)) ++matching;
}

cout << n - matching;
}