Задача A. Максимальный поток (несколько истоков и стоков) ≡

Условие

Требуется найти максимальный поток в сети с несколькими истоками и стоками.

Формат входного файла

В первой строке входного файла содержится число N  — количество вершин в сети. Далее следует N чисел a_i ∈ 0, 1, 2. Если a_i = 0, то i-ая вершина  — это обычный узел; если a_i = 1 то i-ая вершина  — это исток; если a_i = 2 то i-ая вершина  — это сток. Гарантируется, что в сети есть хотя бы один исток и хотя бы один сток.

Далее следует матрица целых чисел U размером N × N. 0 ≤ U_ij ≤ 10⁶  — вместимость ребра из i-ой вершины в j-ую. На диагонали матрицы находятся нули.

Формат выходного файла

В выходной файл выведите единственное число  — объем максимального потока.

Ограничения

2 ≤ N ≤ 50

Примеры тестов

2
1 2
0 100
1000 0

100

4
1 0 0 2
0 2 1 0
0 0 1 2
0 1 0 1
0 0 0 0

3

10
0 0 1 0 1 2 2 0 2 0 
0 100 0 0 0 1 0 0 0 0
0 0 0 0 0 120 0 0 0 0
100 0 0 0 0 0 0 0 0 0
10 10 0 0 0 0 0 20 0 20
0 0 0 50 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 15 0 15 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 10 0 0

141

Задача B. Газовые войны ≡

Условие

Газовая компания должна поставлять потребителям определенный контрактами объем газа, но при транспортировке газ может откачиваться из трубы и в результате потребители могут не получить газ в нужном объеме.

Напишите программу, вычисляющую минимальный объем газа, который нужно поставлять газовой компании, чтобы всем потребителям газ дошел в объеме, определяемом контрактами.

Формат входного файла

Первая строка входного файла содержит три целых числа, разделенных пробелами — количество потребителей N, количество промежуточных насосных станций K и количество труб для транспортировки газа M.

Вторая строка содержит N целых чисел V_i, разделенных пробелами — объемы газа, которые необходимо поставить потребителям.

Далее следует M строк, содержащих по четыре целых числа, разделенных пробелами — номера узлов a_j (0 ≤ a_j ≤ K+N) и b_j (0 ≤ b_j ≤ K+N), связанных трубой, максимальный объем газа f_j, который можно подать на вход этой трубы и процент газа d_j, который выкачивается из этой трубы при транспортировке.

Узел c номером 0 соответствует компании-поставщику. Потребителям соответствуют узлы с номерами от 1 до N. Промежуточные насосные станции имеют номера от N+1 до N+K. Между двумя узлами проходит не более одной трубы.

Формат выходного файла

Ограничения

Примеры тестов

1 1 3
10
0 1 5 20
0 2 10 5
2 1 10 5

11.21875

Задача C. Быстрое двудольное паросочетание ≡

Условие

Напишите программу для нахождения максимального двудольного паросочетания.

Формат входного файла

Входной файл содержит целые числа p, q, m — мощности левой правой доли, а также количество рёбер соответственно.

Далее содержится описание m ребер в виде списка пар целых чисел (u_i, v_i). Наличие пары (u_i, v_i) означает ребро между u_i-ой вершиной левой доли и v_i-ой вершиной правой доли.

Гарантируется, кратных рёбер в графе нет.

Формат выходного файла

Выходной файл должен содержать мощность максимального паросочетания с последующим перечислением рёбер из него в том же формате, что и во входном файле. Если решений несколько, выведите любое.

Ограничения

1 ≤ p, q ≤ 10⁵

1 ≤ m ≤ 2*10⁵

1 ≤ u_i ≤ p

1 ≤ v_i ≤ q

Примеры тестов

3 3 6
1 1
1 2
2 1
2 2
2 3
3 2

3
1 1
2 3
3 2