|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
1593. Strong Connectivity
|
| View Problem Statistics | Submit | Problem added debug |
|
Задан ориентированный граф из n вершин и m1 рёбер. Известно, что в графе есть вершины s и t такие, что все вершины достижимы из s, и из всех вершин достижима t. Также на том же множестве вершин задано другое множество рёбер, состоящее из m2 элементов. Рёбрам из этого множества приписаны некоторые целые веса. Вам необходимо добавить к графу некоторые рёбра из второго множества так, чтобы выполнялись следующие требования:
Входные данные В первой строке находится целое число n (1 ≤ n ≤ 100 000). Во второй строке находится целое неотрицательное число m1. Далее в m1 строках находятся описания ребер исходного графа. Каждое ребро задается номерами начала и конца. В следующей строке находится целое неотрицательное число m2. Далее в m2 строках находятся описания ребер, которые можно добавить. Каждое ребро задаётся номерами начала и конца и своим весом — целым числом от - 109 до 109, включительно. Известно, что 0 ≤ m1 + m2 ≤ 500 000. Выходные данные В первую строку выведите «YES» или «NO» в зависимости от того, существует ли решение задачи. Если решение существует, выведите три строки. В первой из них вывeдите суммарный вес добавленных рёбер. Во второй выведите количество добавленных рёбер. В третьей через пробел выведите номера добавленных рёбер. Рёбра нумеруются с единицы в том порядке, в котором они перечислены во входном файле. Каждое добавленное ребро нужно выводить ровно один раз. Примеры Входные данные 2 Выходные данные YES Входные данные 2 Выходные данные NO Входные данные 4 Выходные данные YES
|
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | Trainings in Perm 2009 / | 07.07.09 Small Contest / |
| 1593. | 1594. B - k-almost monotony | 1595. C - Tiling of Triangles |
| time generating 0.109 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |