Задача A. Максимальный поток (несколько истоков и стоков)
Условие
Требуется найти максимальный поток в сети с несколькими истоками и стоками.
Формат входного файла
В первой строке входного файла содержится число N — количество вершин в сети.
Далее следует N чисел ai ∈ 0, 1, 2. Если ai = 0, то i-ая вершина — это обычный узел;
если ai = 1 то i-ая вершина — это исток;
если ai = 2 то i-ая вершина — это сток.
Гарантируется, что в сети есть хотя бы один исток и хотя бы один сток.
Далее следует матрица целых чисел U размером N × N. 0 ≤ Uij ≤ 106 — вместимость ребра из i-ой вершины в j-ую.
На диагонали матрицы находятся нули.
Формат выходного файла
В выходной файл выведите единственное число — объем максимального потока.
Ограничения
2 ≤ N ≤ 50
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
2
1 2
0 100
1000 0
|
100
|
| 2 |
4
1 0 0 2
0 2 1 0
0 0 1 2
0 1 0 1
0 0 0 0
|
3
|
| 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 символов,
и если да, то вывести номера использованных кубиков.
При этом каждый кубик можно использовать только один раз.
Если решений несколько, выдать любое из них.
Формат входного файла
В первой строке входного файла содержится количество кубиков
N.
Во второй строке — слово, в следующих
N строках — по шесть символов без разделителей,
определяющих буквы на гранях кубиков. (Порядок букв не имеет значения).
Формат выходного файла
Выходной файл должен содержать последовательность из
K различных целых чисел от
1 до
N,
задающих номера кубиков для каждой буквы слова, начиная с первой.
Если решения нет, выходной файл должен содержать единственное число 0.
Ограничения
1 ≤ N, K ≤ 12.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS
|
2 5 3 4
|
