Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 319 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#21
Электрички на перегонах не меняют
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

На пригородной железной дороге N станций и M соединяющих их перегонов. Любые две станции соединены не более чем одним перегоном. Сеть перегонов устроена так, что, отправившись от любой станции, можно вернуться на нее, только проехав хотя бы один перегон дважды. На железной дороге организовано движение электричек. Каждая электричка ходит в обоих направлениях по своему маршруту между двумя конечными станциями и останавливается на всех промежуточных станциях

Для удобства пассажиров руководство железной дороги решило ввести новую систему оплаты проезда. По этой системе каждой станции присваивается некоторое целое число, называемое тарифным номером этой станции. Стоимость проезда между двумя станциями без пересадок определяется модулем разности тарифных номеров этих станций. Тарифные номера станций вдоль маршрута каждой электрички должны изменяться монотонно, то есть при движении в каком-либо направлении строго возрастать и, следовательно, строго убывать при движении в обратном направлении. Это обеспечивает рост стоимости проезда с увеличением количества пройденных перегонов.

Требуется написать программу, которая назначит каждой станции тарифный номер.

1

4 станции, 3 перегона: 1-4, 2-4, 3-4

Маршруты: 1-4-2, 2-4-3, 3-4-1.


Ответ: решения нет

2

5 станций, 4 перегона: 1-5, 2-5, 3-5, 4-5

Маршруты: 1-5-2, 2-5-3, 3-5-4, 4-5-1.


Ответ: решение есть; например, следующее: номер станции: 1 2 3 4 5

тарифный номер: 1 4 1 5 3


Замечание: тарифные номера разных станций могут совпадать.
Входные данные

В первой строке входных данных содержатся два целых числа: N — количество станций (2 ≤ N ≤ 100 000), и M — количество перегонов между ними (1 ≤ M ≤ N – 1). В последующих M строках записаны пары целых чисел a, b (a ≠ b, 1 ≤ a ≤ N, 1 ≤ b ≤ N), означающие наличие перегона между станциями a и b. За ними в отдельной строке записано единственное целое положительное число K — количество маршрутов электричек. В последующих K строках идут описания маршрутов электричек, по одному на строке. Каждое описание представляет собой последовательность целых чисел — номеров всех станций маршрута в порядке одного из двух возможных направлений следования электрички. Описание маршрута заканчивается числом 0.

Все номера станций в описании маршрута различны. Количество станций в каждом маршруте не менее двух. Любые две последовательные станции в маршруте каждой электрички соединены перегоном. Суммарное количество станций в описаниях всех маршрутов не превосходит 200 000. Могут быть станции и перегоны, через которые не проходит ни одна электричка.

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

В первую строку  выведите «NO», если искомого назначения тарифных номеров не существует. В противном случае в первую строку выведите «YES», а в следующей строке — N целых положительных чисел, где i-е число — тарифный номер i-й станции. Тарифный номер каждой станции должен находиться в диапазоне от 1 до N.

Если существует несколько решений, необходимо вывести любое из них.

Система оценивания

Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

  • Группа 1 (20 баллов): N, K <= 20
  • Группа 2 (30 баллов): N, K <= 2000
  • Группа 3 (50 баллов): без дополнительных ограничений
Примеры
Входные данные
6 5
1 2
5 2 
5 6
4 5
3 2
6
1 2 0
5 6 0
3 2 1 0
5 2 3 0
4 5 2 0
6 5 4 0
Выходные данные
YES
2 3 4 1 2 3
#31
Роботы
  
ограничение по времени на тест
20.0 second;
ограничение по памяти на тест
64 megabytes
Задан невзвешенный граф. По графу перемещаются роботы, для которых заданы начальные вершины. Требуется определить, через какое время все роботы встретятся в какой либо вершине или середине ребра.

В подземелье есть N залов, соединенных туннелями. В некоторых залах находятся роботы, которые одновременно получили команду собраться в одном месте.

Роботы устроены так, что, получив команду, они все начали двигаться с такой скоростью, что туннель между двумя любыми залами преодолевают за 1 минуту. Роботы не могут останавливаться (в том числе и в залах), а также менять направление движения, находясь в туннелях (однако попав в зал, робот может из него пойти по тому же туннелю, по которому он пришел в этот зал).

Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).

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

Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.

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

Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).

Оценка задачи

1 балл получат программы, правильно решающие задачу в случае, когда встреча роботов произойдет в зале, при ограничениях N≤100, K≤2000, M≤100.

Примеры
Входные данные
4 5
1 2
2 3
3 4
1 4
1 3
3
1 2 4
Выходные данные
1
Входные данные
3 2
1 2
2 3
2
1 3
Выходные данные
1
#34
Разрезанный прямоугольник
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости нарисовали прямоугольник, после чего его разрезали прямыми. Напишите программу, которая вычислит, сколько из полученных кусков исходного прямоугольника имеют треугольную форму.

 4
Рисунок, соответствующий 1-му примеру входных и выходных данных

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

Сначала на вход программы поступают два положительных числа X и Y, задающих координаты правого верхнего угла прямоугольника. Прямоугольник расположен в системе координат так, что левый нижний его угол имеет координаты 0,0 и стороны параллельны осям координат.

Далее вводится целое число N — количество разрезов (1≤N≤200). Затем описываются сами разрезы. Каждый разрез делался вдоль некоторой прямой. Каждая прямая, соответствующая разрезу, задается тремя числами A, B, C такими, что все точки (x,y) этой прямой (и только они) удовлетворяют уравнению Ax+By+C=0 (при этом всегда A2+B2>0).

Все входные данные (кроме N) –  вещественные числа, заданы с двумя знаками после десятичной точки и не превышают 104. Никакие две прямые не совпадают между собой и не содержат сторон прямоугольника. Каждый разрез проходит через точки внутри исходного прямоугольника.

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

Выведите одно целое число — количество частей исходного прямоугольника, имеющих треугольную форму.

Система оценки

1 балл получат программы, правильно решающие задачу при ограничении 1≤N≤50.

Примеры
Входные данные
5.00 1.00
3
1.00 -2.00 0.00
1.00 -3.00 -2.00
1.00 1.00 -4.00
Выходные данные
3
Входные данные
4.00 2.00
2
1.00 -2.00 0.00
1.00 2.00 -4.00
Выходные данные
4
#42
Красно-синий граф
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задано N точек. Из каждой точки исходят красные или синие ребра во все точки с большим номером. Требуется определить, существует ли пара точек такая, что из первой можно добраться до второй как по красным ребрам так и по синим.

Даны N точек, занумерованных числами 1, 2, ..., N. От каждой точки с меньшим номером к каждой точке с большим номером ведет стрелка красного или синего цвета. Раскраска стрелок называется однотонной, если нет двух таких точек A и B, что от A до B можно добраться как только по красным стрелкам, так и только по синим.

Ваша задача — по заданной раскраске определить, является ли она однотонной.

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

В первой строке входных данных содержится единственное число N (3 ≤ N ≤ 5000).

В следующих N–1 строках идет описание раскраски. В (i+1)-й строке  записано (N–i) символов R (красный) или B (синий), соответствующих цвету стрелок, выходящих из точки i и входящих в точки (i+1), (i+2), ..., N соответственно.

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

Выведите YES, если приведенная раскраска является однотонной, и NO в противном случае.

Оценка задачи

1 балл будут набирать решения, верно работающие для N ≤ 50.

Примеры
Входные данные
3
RB
R
Выходные данные
NO
Входные данные
3
RR
R
Выходные данные
YES
#95
Флойд вместо Дейкстры
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти длину кратчайшего пути из вершины s в вершину t.

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

В первой строке заданы три числа: число вершин в графе N ≤50, номера вершин s и t. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от 0 до 1000000, число -1 означает отсутствие соответствующего ребра. Гарантируется, что на главной диагонали матрицы стоят нули.

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

Выведите одно число – минимальную длину пути. Если пути не существует, выведите -1.

Примеры
Входные данные
3 1 2
0 -1 3
7 0 1
2 -1 0
Выходные данные
-1
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест