 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Формат входного файла
Первая строка входного файла содержит два целых числа: n и p — исходное количество предприятий (2 ≤ n ≤ 100 000). Вторая строка входного файла содержит n целых чисел a 1, a 2, …, an — длины исходных отрезков реки. Третья строка входного файла содержит целое число k — количество событий, происходивших с предприятиями (1 ≤ k ≤ 100 000). Последующие k строк содержат описания событий, i -я строка содержит два целых числа: ei и vi — тип события и номер предприятия, с которым оно произошло. Значение ei = 1 означает, что предприятие, которое после всех предыдущих событий является vi -м по порядку, если считать с единицы от истока реки, обанкротилось, а значение ei = 2 означает, что это предприятие разделилось на два. Гарантируется, что значение vi не превышает текущее количество предприятий. Гарантируется, что если отрезок предприятия при банкротстве или разделении требуется поделить на две части, то он имеет длину большую или равную 2. Гарантируется, что если на реке осталось единственное предприятие, оно не банкротится.
Формат выходного файла
Выходной файл должен содержать (k + 1) целых чисел, по одному в строке. Первая строка должна содержать исходную сумму квадратов длин отрезков реки, а каждая из последующих k строк — сумму квадратов длин отрезков реки после очередного события.
Пример входных и выходных файлов
| river.in | river.out |
| 4 0 3 5 5 4 1 1 2 1 1 3 2 2 1 3 |
Лабораторная работа «Максимальный поток в сети»
Входной файл: input.txt
Выходной файл: output.txt
Ограничение времени: 2 секунды на тест
Найти максимальный поток в заданной транспортной сети.
Вход
В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 500). Остаток файла содержит список ребер графа. Каждое ребро задано тройкой целых чисел u, v, c (1 ≤ u, v ≤ N, 0 < c ≤ 10000), где u, v - номера вершин, c – пропускная способность ребра (u, v). Источник сети - вершина 1, сток сети - вершина N.
Замечание
Сеть является ориентированным графом.
Выход
В выходной файл запишите величину максимального потока и матрицу потока.
Примеры входа и выхода
| input.txt | output.txt |
| 1 2 1 2 3 1 3 6 1 5 6 1 2 5 1 4 3 1 1 4 1 | 0 1 0 1 0 0 -1 0 0 0 1 0 0 0 0 -1 0 1 -1 0 1 0 0 0 0 -1 0 0 0 1 0 0 -1 0 -1 0 |
Лабораторная работа «Максимальный поток минимальной стоимости»
Входной файл: input.txt
Выходной файл: output.txt
Ограничение времени: 5 секунд на тест
Дана сеть, в которой каждому ребру помимо пропускной способности приписана неотрицательная стоимость. Найти максимальный поток в сети, имеющий минимальную суммарную стоимость.
Вход
В первой строке входного файла записано количество вершин сети N (1 ≤ N ≤ 500), источник сети S и сток сети T (1 ≤ S, T ≤ N, S ≠T). В остальных строках записан список рёбер сети. Каждое ребро задано четвёркой целых чисел u, v, c, w (1 ≤ u, v ≤ N, 0 < c, w ≤ 10000), где u, v - номера вершин, c - пропускная способность ребра (u, v), w – стоимость пропуска единичного потока через ребро (u, v).
Поиск по сайту: