Новогодняя вечеринка решение через графы кратко

Привет, сегодня поговорим про новогодняя вечеринка решение через графы, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое новогодняя вечеринка решение через графы , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

USA Computing Olympiad, 2002

Задание

Группа из N (1

Координатор коровьей вечеринки хочет максимизировать общее количество блюд, которые будут принесены на вечеринку, но имеет установленный лимит на количество блюд каждого типа. Каждая корова может принести К (1 <= К <= 5) блюд, но они должны отличаться друг от друга. К примеру, одна корова не может принести 3 пирожка с говядиной, но может принести пирожок, хлеб и вкусную люцерну в апельсиновом соусе. Каково максимальное количество пищи, которую коровы могут принести на вечеринку?

Ввод

Строка 1: Три целых числа: N, К, D
Строка 2: D неотрицательных чисел — предел суммарного количества для каждого из различных блюд, которые могут быть принесены на вечеринку.
Строки 3..N+ 2: Каждая строка содержит начальное целое Z (1<=Z<=D), обозначающее количество типов различных блюд, которое может приготовить одна корова; остаток строки содержит Z целых чисел — идентификаторов типов пищи, которую может приготовить корова, соответствующая текущей строке (в строке 3 — корова 1, в строке 4 — корова 2, и т. д.).

Пример ввода [файл party.in]: 
4 3 5 
2 2 2 2 3 
4 1 2 3 4 
4 2 3 4 5 
3 1 2 4 
3 1 2 3 

Пояснения к примеру:

Данные      Пояснения 
4 3 5       4 коровы, каждая до 3 блюд, всего 5 различных типов пищи 
2 2 2 2 3   max — 2 блюда типов 1..4 и 3 блюда типа 5 
4 1 2 3 4   1-я корова может приготовить 4 различных блюда A, 2, 3, 4) 
4 2 3 4 5   2-я корова может приготовить 4 различных блюда B, 3, 4, 5) 
3 1 2 4     3-я корова может приготовить 3 различных блюда A, 2, 4) 
3 1 2 3     4-я корова может приготовить 3 различных блюда A, 2, 3) 

Вывод

Одна строка содержит одно целое число — максимальное количество блюд, которое может быть принесено на вечеринку.

Пример вывода:
9

Пояснения:
Корова 1 принесет блюда 3 и 4:
Корова 2 принесет блюда 3. Об этом говорит сайт https://intellect.icu . 4 и 5:
Корова 3 принесет блюда 1 и 2;
Корова 4 принесет блюда 1 и 2.

Решение [вверх]

Рассмотрим граф, состоящий из N + D вершин. Вершины с номерами от 1 до N соответствуют коровам, вершины с номерами от N+1 до N+D соответствуют различным видам пищи (блюдам).

Прежде всего мы должны добавить в граф вершины исток (вершину с номером start = N+D+1) и сток (вершину с номером Finish = N + D + 2). Понятно, что от истока должны быть дуги ко всем вершинам 1..N(коровам), а от вершин N+1..N+D (блюда) должны быть дуги к стоку. Каковы же должны быть веса введенных дуг от истока и к стоку? Для дуг «от истока»: c[start, i] - К (для всех i от 1 до N), поскольку каждая корова может принести К блюд. Для дуг «к стоку»: c[i, Finish] - Lim[i-N] (для всех i от N + 1 до N + D), поскольку имеется лимит на количество блюд каждого типа.

Мы строим дугу от коровы i к блюду j в том и только в том случае, если корова i может приготовить блюдо j. Вес каждой такой дуги должен получить значение 1, поскольку блюда, которые принесет корова, должны отличаться друг от друга.

Далее с помощью алгоритма Форда-Фалкерсона находим максимальный поток из истока (вершина start) к стоку (вершина finish). Значение максимального потока и будет искомым значением количества блюд.

Граф, полученный для данной задачи

Формальное описание

Party()
1. Считать входные данные задачи из файла.
2. Создать вершину-исток и соединить ее с вершинами графа, которые 
   отвечают коровам. Пропускная способность для этих  ребер равна 
   значению ограничению по блюдам для каждой коровы.
3. Создать вершину-сток и соединить ее с вершинами-блюдами. 
   Пропускная способность равняется ограничению по каждому блюду.
4. Найти максимальный поток по алгоритму Форда-Фалкерсона между истоком 
   и стоком.
5. Найти блюда, приготовленные каждой коровой.
6. Подсчитать количество разных блюд.

На этом все! Теперь вы знаете все про новогодняя вечеринка решение через графы, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое новогодняя вечеринка решение через графы и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов