ограничение по времени на тест: 5 секунд
ограничение по памяти на тест: 512 мегабайт
ввод: mincost.in
вывод: mincost.out
Задан ориентированный граф, каждое ребро которого обладает пропускной способностью и стоимостью. Найдите максимальный поток минимальной стоимости из вершины с номером 1 в вершину с номером n.
Первая строка входного файла содержит n и m — количество вершин и количество ребер графа (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000). Следующие m строк содержат по четыре целых числа числа: номера вершин, которые соединяет соответствующее ребро графа, его пропускную способность и его стоимость. Пропускные способности и стоимости не превосходят 10^5.
В выходной файл выведите одно число — цену максимального потока минимальной стоимости из вершины с номером 1 в вершину с номером n. Ответ не превышает 2^63 - 1. Гарантируется, что в графе нет циклов отрицательной стоимости.
входные данные
4 5
1 2 1 2
1 3 2 2
3 2 1 1
2 4 2 1
3 4 2 3выходные данные
12ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дана целочисленная матрица C размера n × n. Требуется выбрать n ячеек так, чтобы в каждой строке и каждом столбце была выбрана ровно одна ячейка, а сумма значений в выбранных ячейках была минимальна.
Первая строка входного файла содержит n (2 ≤ n ≤ 300). Каждая из последующих n строк содержит по n чисел: Cij Все значения во входном файле неотрицательны и не превосходят 10^6.
В первую строку выходного файла выведите одно число — искомая минимизуруемая величина. Далее выведите n строк по два числа в каждой — номер строки и столбца клетки, участвующей в оптимальном назначении.
входные данные
3
3 2 1
1 3 2
2 1 3выходные данные
3
2 1
3 2
1 3ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дано дерево без корня с N вершинами, являющееся связным, неориентированным графом с N вершинами, пронумерованными с 1 до N, и N - 1 ребрами. i-е ребро соединяет вершины Ai и Bi.
Вы хотите отметить каждую вершину числом от 1 до K, включительно так, чтобы потратить как можно меньше денег. Отметить i-ю вершину числом j, стоит Ci, j долларов.
Также, после того, как все дерево было отмечено, вы должны заплатить еще P долларов за каждую вершину, которая имеет как минимум одну пару соседей, отмеченных одним числом. Другими словами, за каждую вершину u, вы должны заплатить P долларов если существуют две другие вершины v и w, смежные с u, такие, что числа, которыми отмечены v и w, одинаковы (заметим, что число, которым отмечена u, не важно). Вы платите штраф в P долларов один раз для данной центральной вершины u, даже если существует несколько пар соседей, удовлетворяющих вышеописанному условию.
Какая минимальная стоимость (в долларах) отметки всех N вершин?
В первой строчке содержатся натуральные числа N (1 ≤ N ≤ 1000), K (1 ≤ K ≤ 30), и P (0 ≤ P ≤ 10^6), отделенные пробелом. Затем, N строчек, i-я из которых содержит разделенные пробелом числа от Ci, 1 до Ci, K (0 ≤ Ci, j ≤ 10^6). Далее, N - 1 строчка, i-я из которых содержит два разделенных пробелом числа Ai и Bi (1 ≤ Ai, Bi ≤ N).
Выведите минимальную стоимость отметки всех вершин дерева.
входные данные
1 1 1
111выходные данные
111входные данные
3 1 8
1
2
4
1 2
2 3выходные данные
15входные данные
3 2 10
4 7
8 9
2 3
1 2
2 3выходные данные
15входные данные
4 2 99
0 1
0 1
0 1
0 0
4 1
2 4
4 3выходные данные
99входные данные
4 3 99
0 1 0
0 1 0
0 1 0
0 0 0
4 1
2 4
4 3выходные данные
1ограничение по времени на тест: 1 секунда
ограничение по памяти на тест: 512 мегабайт
ввод: rps2.in
вывод: rps2.out
Год назад Ростислав с Мирославом играли в камень, ножницы, бумагу на щелбаны. За каждый выигранный раунд победитель ставил один щелбан проигравшему. В случае ничьи щелбаны не ставились. Эта игра запомнилась Мирославу как самая худшая игра в его жизни: всю следующую неделю у него болел лоб.
Воспоминания нахлынули на Мирослава, когда он нашел бумажку с шестью числами — запись с той самой игры. Прошло много времени, и теперь Мирослав может спокойно подумать, почему он проиграл так много раз. Но, к сожалению, он не может посчитать точное количество своих поражений, так как он записал только то, что Ростислав показал камень r1 раз, ножницы s1 раз и бумагу p1 раз, а сам Мирослав показал камень r2 раз, ножницы s2 раз и бумагу p2 раз.
Помогите Мирославу узнать по этим данным, какое минимальное количество щелбанов он мог получить в той самой роковой игре.
Для справки, победитель этой игры определяется по следующим правилам: • Камень побеждает ножницы («камень затупляет или ломает ножницы»); • Ножницы побеждают бумагу («ножницы разрезают бумагу»); • Бумага побеждает камень («бумага накрывает камень»).
Если игроки показали одинаковый знак, то засчитывается ничья.
В первой строке входных данных три целых числа r1, s1, p1. Во второй строке три целых числа r2, s2, p2.
Все числа неотрицательные и не превышают 10^8, r1 + s1 + p1 = r2 + s2 + p2.
Выходные данные должны содержать единственное число — минимальное количество щелбанов, которые мог получить Мирослав.
входные данные
3 0 0
0 3 0выходные данные
3ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: rps2.in
вывод: rps2.out
Есть n городов. Между городами есть ориентированные дороги, у каждой дороги есть стоимость покупки разрешения на проезд. Мы хотим торговать во всех городах. У нас есть неограниченное кол-во коммивояжеров. Для каждого из них мы должны определить список городов, в которых они будут торговать. Каждый коммивояжер будет объезжать все города из своего списка по циклу (он может по пути заезжать в другие города, но не торговать там). Если два (или более) коммивояжеров будут ездить по одной дороге, то каждому из них мы должны купить разрешение на проезд. Если список у коммивояжера состоит только из одного города, то он либо должен регулярно выезжать из города (тоже по какому-то циклу), либо мы должны купить ему прописку (у каждого города есть цена прописки). Наконец, в любом городе должен торговать только один коммивояжер, иначе предприятием заинтересуется налоговая. Нужно минимизировать издержки.
В первой строке два числа n, m — количество городов и количество дорог (1 ≤ n ≤ 256, 0 ≤ m ≤ n(n - 1)).
Во второй строке n чисел ai — цена прописки для города номер i (0 ≤ ai ≤ 10^9).
Затем в m строках описаны дороги. Описание дороги из города u в город v со стоимостью разрешения на проезд c выглядит как u v cost (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ c ≤ 10^9). Гарантируется, что между любой парой городов не более 1 дороги в каждом из направлений.
Выведите одно число — минимальную сумму издержек.
входные данные
3 3
30 25 30
1 2 3
2 3 5
3 1 10выходные данные
18