Олимпиадный тренинг

Задача . G. Очередная задача про максимальный поток


Задача

Темы: графы Потоки Структуры данных *2700

В этой задаче вам придётся иметь дело с очень специфичной ориентированной сетью (взвешенным ориентированным графом).

Сеть состоит из двух частей: части A и части B. Каждая часть состоит из n вершин; i-ю вершину части A будем обозначать как Ai, а i-ю вершину части B — как Bi.

Для каждого i (1 ≤ i < n) существует ориентированное ребро из Ai в Ai + 1, а также из Bi в Bi + 1. Пропускные способности этих рёбер заданы во входных данных. Также может быть несколько рёбер, ведущих из A в B (но нет таких рёбер, которые ведут из B в A).

Вам необходимо посчитать величину максимального потока из A1 в Bn в данной сети. Пропускные способности рёбер, ведущих из Ai в Ai + 1, также могут иногда меняться, и вам нужно пересчитывать величину потока после этих изменений. Вся остальная часть сети фиксирована (не происходит никаких изменений в части B, никаких изменений рёбер, ведущих из A в B, никакие рёбра не добавляются и не удаляются).

Посмотрите на пример и пояснение к нему, чтобы лучше понять структуру сети.

Входные данные

В первой строке записаны три числа n, m и q (2 ≤ n, m ≤ 2·105, 0 ≤ q ≤ 2·105) — количество вершин в каждой части, количество рёбер, ведущих из A в B, и количество изменений соответственно.

Далее следуют n - 1 строк. В i-й строке записаны два числа xi и yi, обозначающих, что ребро из Ai в Ai + 1 имеет пропускную способность xi, а ребро из Bi в Bi + 1 имеет пропускную способность yi (1 ≤ xi, yi ≤ 109).

В следующих m строках указываются рёбра из A в B. Каждая строка содержит три целых числа x, y и z, обозначающих ребро из Ax в By с пропускной способностью z (1 ≤ x, y ≤ n, 1 ≤ z ≤ 109). Может быть несколько рёбер, ведущих из Ax в By.

В последних q строках обозначаются изменения, вносимые в сеть. В i-й из этих строк записаны два числа vi и wi, обозначающих, что пропускная способность ребра из Avi в Avi + 1 становится равной wi (1 ≤ vi < n, 1 ≤ wi ≤ 109).

Выходные данные

Сначала выведите величину максимального потока в исходной сети. Затем выведите q чисел, i-е из которых должно быть равно величине максимального потока после i-го изменения.

Примечание

В примере до всех изменений сеть выглядит так:


Примеры
№Входные данныеВыходные данные
1 4 3 2
1 2
3 4
5 6
2 2 7
1 4 8
4 3 9
1 100
2 100 
9
14
14

time 4000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python1
С++ Mingw-w644
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет