В маленьком провинциальном городке есть маленькая школа, в которой учатся не совсем большие дети. После занятий они бегут на автобусную остановку, откуда автобус развозит их по домам.
По дороге от школы до остановки есть N перекрестков, соединенных улицами. Школьники с улицы на улицу переходят только на перекрестках.
Все школьники, как известно, любят мороженое. Известная компания Cold-N-Icy, производящая мороженое, решила воспользоваться этим. Она хочет разместить киоски с мороженым на некоторых перекрестках таким образом, чтобы любой путь школьника от школы до остановки проходил хотя бы через один перекресток, на котором установлен киоск.
Так как установка и содержание киоска — дорогое дело, то компания решила привлечь Вас для того, чтобы определить минимальное число киосков, которое необходимо установить.
Помогите компании Cold-N-Icy найти это минимальное число.
В первой строке входного файла находится число перекрестков N (1 ≤ N ≤ 100).
В каждой из последующих N строк находится информация о перекрестках, соединенных улицами между собой. Перекрестки нумеруются, начиная с единицы. В начале i-той строки находится число Ki – количество мест (перекрестков, школы или остановки), соединенных улицами с i-тым перекрестком. Далее идет Ki мест, разделенных пробелами. Для обозначения перекрестков используются их номера, школа обозначается как school, остановка обозначается как station.
Если перекресток i находится в списке перекрестка j, то обратное также верно.
Гарантируется, что от школы до остановки всегда существует путь.
Выведите одно число — минимальное число киосков, которые планируется установить.
2 2 school station 2 station school
2
Эта задача настолько проста, что у нее нет даже условия.
Дано N вершин неориентированного графа, M ребер, пропускная способность которых равна 1, и K запросов. Каждая вершина задается строкой, состоящей из маленьких латинских букв, длиной не более 10 символов. Для каждого запроса найдите величину максимального потока из одной вершины в другую. Вот и все.
В первой строке входного файла вводится 3 целых числа: N (1<=N<=5*10^5), M (0<=M<=5*10^5) и K (0<=K<=1000). Далее следует M строк, в каждой из которых через пробел записаны имена 2-ух вершин, что означает, что из одной вершины в другую есть ребро. Далее следует K запросов в том же виде, в котором задаются ребра. Запрос означает, что нужно вывести величину максимального потока из одной вершины в другую. Ответ на каждый запрос нужно выводить в отдельной строке. Гарантируется, что на вход поступает не более 2 запросов, при которых величина максимального потока положительна.
Выведите ответ на поставленную задачу в указанном в условии формате.
7 11 1 smity grepik dop grepik smity rojer rojer dop dop jack sanek jack dop sanek hello sanek hello grepik dop hello rojer jack smity sanek
2
Дан двудольный граф, в каждой из долей которого \(N\) вершин. В нем также есть \(M\) ребер, каждое из которых имеет свою стоимость. Требуется найти паросочетание максимальной стоимости.
В первой строке входного файла заданы числа \(1 \leq N \leq 50\) и \(1 \leq M \leq 1000\). В следующих \(M\) строках заданы ребра графа – в каждой по три числа. Первые два из них задают соответственно номера вершин в левой и правой долях, третье – стоимость. Все стоимости не превосходят 10. Гарантируется, что у каждых двух ребер есть отличие хотя бы в одном из концов.
В первой строке выходного файла выведите максимальную стоимость. В следующей строке выведите \(N\) чисел, i-ое из которых обозначает номер вершины из правой доли, с которой соединена i-ая вершина левой доли. Если i-ая вершина не соединена ни с какой вершиной правой доли, то на i-ом месте должна стоять -1. Из всех возможных ответов нужно вывести наименьший лексикографически. Один ответ считается лексикографически меньшим другого, если первое число, в котором они отличаются у него меньше.
3 5 1 1 1 2 2 1 3 3 1 2 1 2 3 2 2
4 -1 1 2
Вася очень любит различные игры: шашки, шахматы, домино, крестики-нолики и т. д. Поскольку он играет в них уже достаточно давно, он успел изучить эти игры достаточно хорошо, и они стали скучными. Поэтому он теперь изобретает новые игры на основе тех, в которые уже наигрался. Недавно он изобрел игру «Доминошахматы».
Она состоит в следующем: Вася берет у дедушки большой кусок фанеры и раскрашивает его так, что у него получается шахматная доска размера N × M клеточек. Потом он берет кости домино и пытается покрыть ими полученную доску так, чтобы все клеточки были закрыты, не было наложений и никакие доминошки не торчали за края доски (каждая доминошка покрывает две соседние клетки).
Поскольку Вася не спрашивает разрешения у дедушки прежде, чем взять доску, он иногда берет ненужные доски, а иногда и те, которые дедушка хотел использовать в строительстве новой дачи. Как раз сегодня Вася взял «нужную» доску, поэтому дедушка был вынужден вырезать из Васиной доски два квадрата по одной клеточке.
Вася сначала огорчился, что не сможет поиграть в свою игру. А потом решил попробовать замостить доску с уже вырезанными клетками, причем так, чтобы вырезанные клетки не были накрыты доминошками.
Помогите Васе понять, можно ли это сделать.
В первой строке входных данных записаны числа N и M — размеры доски (1 ≤ N ≤ 200, 1 ≤ M ≤ 200, N·M > 2).
Во второй строке вводятся через пробел два целых числа — координаты x1 и y1 первой вырезанной клетки (1 ≤ x1 ≤ N, 1 ≤ y1 ≤ M).
В третьей строке вводятся через пробел два целых числа — координаты x2 и y2 второй вырезанной клетки (1 ≤ x2 ≤ N, 1 ≤ y2 ≤ M).
Первая и вторая клетки не совпадают.
Выведите «YES», если доску с вырезанными клеточками можно покрыть доминошками, и «NO» в противном случае. (Запас доминошек у Васи бесконечный.)
2 2 1 1 2 2
NO
2 2 1 1 1 2
YES