Ограничение по времени на тест: 5 секунд
Ограничение по памяти на тест: 1024 мегабайта
ввод: стандартный ввод
вывод: стандартный вывод
Дан неориентированный граф, состоящий из N вершин и M ребер.
У каждого ребра которого есть маленькая пропускная способность. Между любой парой вершин может быть больше одного ребра.
Исток находится в вершине 1, а сток в вершине N. Требуется найти максимальный поток между истоком и стоком.
В первой строке записано натуральное число N — число вершин (2 ≤ N ≤ 100).
Во второй строке записано натуральное число M — число ребер (1 ≤ M ≤ 5000).
Далее в M строках идет описание ребер. Каждое ребро задается тройкой целых чисел Ai, Bi, Ci, где Ai, Bi — номера вершин, которые соединяет ребро (Ai≠Bi), а Ci (0 ≤ Ci ≤ 20) — пропускная способность этого ребра.
Выведите максимальный поток между вершинами с номерами 1 и N.
Входные данные
2
2
1 2 1
2 1 3
Выходные данные
4
Ограничение по времени на тест: 5 секунд
Ограничение по памяти на тест: 1024 мегабайта
ввод: стандартный ввод
вывод: стандартный вывод
Дана система из узлов и труб, по которым может течь вода. Для каждой трубы известна наибольшая скорость, с которой вода может протекать через нее. Известно, что вода течет по трубам таким образом, что за единицу времени в каждый узел (за исключением двух — источника и стока) втекает ровно столько воды, сколько из него вытекает.
Ваша задача — найти наибольшее количество воды, которое за единицу времени может протекать между источником и стоком, а также скорость течения воды по каждой из труб.
Трубы являются двусторонними, то есть вода в них может течь в любом направлении. Между любой парой узлов может быть более одной трубы.
В первой строке записано натуральное число N — количество узлов в системе (2≤ N ≤100). Известно, что источник имеет номер 1, а сток номер N. Во второй строке записано натуральное M (1≤ M ≤5000) — количество труб в системе. Далее в M строках идет описание труб. Каждая труба задается тройкой целых чисел Ai, Bi, Ci, где Ai, Bi — номера узлов, которые соединяет данная труба (Ai≠Bi), а Ci (0≤ Ci ≤ 10^4) — наибольшая допустимая скорость течения воды через данную трубу.
В первой строке выведите наибольшее количество воды, которое протекает между источником и стоком за единицу времени. Далее выведите M строк, в каждой из которых выведите скорость течения воды по соответствующей трубе. Если направление не совпадает с порядком узлов, заданным во входных данных, то выводите скорость со знаком минус. Числа выводите с точностью 10^−3.
Входные данные
2
2
1 2 1
2 1 3
Выходные данные
4
1
-3
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 1024 мегабайта
ввод: стандартный ввод
вывод: стандартный вывод
Найдите минимальный разрез между вершинами 1 и n в заданном неориентированном графе.
На первой строке входного файла содержится n (2≤ n ≤100) — число вершин в графе и m (0≤ m ≤400) — количество ребер. На следующих m строках входного файла содержится описание ребер. Ребро описывается номерами вершин, которые оно соединяет, и его пропускной способностью (положительное целое число, не превосходящее 10000000), при этом никакие две вершины не соединяются более чем одним ребром.
На первой строке выходного файла должны содержаться количество ребер в минимальном разрезе и их суммарная пропускная способность. На следующей строке выведите возрастающую последовательность номеров ребер (ребра нумеруются в том порядке, в каком они были заданы во входном файле).
Входные данные
3 3
1 2 3
1 3 5
3 2 7
Выходные данные
2 8
1 2
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 1024 мегабайта
ввод: стандартный ввод
вывод: стандартный вывод
Две улиточки Маша и Петя сейчас находятся в на лужайке с абрикосами и хотят добраться до своего домика. Лужайки пронумерованы числами от 1 до n и соединены дорожками (может быть несколько дорожек соединяющих две лужайки, могут быть дорожки, соединяющие лужайку с собой же). По соображениям гигиены, если по дорожке проползла улиточка, то вторая по той же дорожке уже ползти не может. Помогите Пете и Маше добраться до домика.
В первой строке файла записаны четыре целых числа — n, m, s и t (количество лужаек, количество дорог, номер лужайки с абрикосами и номер домика). В следующих m строках записаны пары чисел. Пара чисел (x, y) означает, что есть дорожка с лужайки x до лужайки y (из-за особенностей улиток и местности дорожки односторонние). Ограничения: 2 ≤ n ≤ 10^5, 0 ≤ m 10^5, s≠t.
Если существует решение, то выведите YES и на двух отдельных строчках сначала последовательность лужаек для Машеньки (дам нужно пропускать вперед), затем путь для Пети. Если решения не существует, выведите NO. Если решений несколько, выведите любое.
Входные данные
3 3 1 3
1 2
1 3
2 3
Выходные данные
YES
1 3
1 2 3
Дан орграф, найти два непересекающихся по ребрам пути из s в t, вывести вершины найденных путей.
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 1024 мегабайта
ввод: стандартный ввод
вывод: стандартный вывод
У короля Людовика двое сыновей. Они ненавидят друг друга, и король боится, что после его смерти страна будет уничтожена страшными войнами. Поэтому Людовик решил разделить свою страну на две части, в каждой из которых будет властвовать один из его сыновей. Он посадил их на трон в города A и B, и хочет построить минимально возможное количество фрагментов стены таким образом, чтобы не существовало пути из города A в город B.
Страну, в которой властвует Людовик, можно упрощенно представить в виде прямоугольника m × n. В некоторых клетках этого прямоугольника расположены горы, по остальным же можно свободно перемещаться. Кроме этого, ландшафт в некоторых клетках удобен для строительства стены, в остальных же строительство невозможно.
При поездках по стране можно перемещаться из клетки в соседнюю по стороне, только если ни одна из этих клеток не содержит горы или построенного фрагмента стены.
В первой строке входного файла содержатся числа m и n (1 ≤ m, n ≤ 50). Следующие m строк по n символов задают карту страны. Символы обозначают: «#» — гора, «.» — место, пригодное для постройки стены, «-» — место, не пригодное для постройки стены, «A» и «B» — города A и B.
В первой строке выходного файла должно быть выведено минимальное количество фрагментов стены F, которые необходимо построить. Далее нужно вывести карту в том же формате, как во входном файле. Клетки со стеной обозначьте символом «+».
Если невозможно произвести требуемую застройку, то выведите в выходной файл единственное число - 1.
Входные данные
5 5
--...
A-.#-
.#.#-
--.--
--.-B
Выходные данные
3
--+..
A-+#-
+#.#-
--.--
--.-B
Входные данные
1 2
AB
Выходные данные
-1
Входные данные
2 2
A#
#B
Выходные данные
0
A#
#B